sys/src/cmd/ip/ppp/block.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <ip.h>
   4 #include <auth.h>
   5 #include "ppp.h"
   6
   7 enum
   8 {
   9         PAD     = 128,
  10         NLIST   = (1<<5),
  11         BPOW    = 10,
  12 };
  13
  14 typedef struct Barena Barena;
  15 struct Barena
  16 {
  17         QLock;
  18         Block*  list[NLIST];
  19 };
  20 static Barena area;
  21
  22 #define ADEBUG if(0)
  23
  24
  25 /*
  26  *  allocation tracing
  27  */
  28 enum
  29 {
  30         Npc=    64,
  31 };
  32 typedef struct Arefent Arefent;
  33 struct Arefent
  34 {
  35         uint    pc;
  36         uint    n;
  37 };
  38 typedef struct Aref Aref;
  39 struct  Aref
  40 {
  41         Arefent tab[Npc];
  42         QLock;
  43 };
  44 Aref arefblock;
  45
  46 static ulong    callerpc(void*);
  47 static void     aref(Aref*, ulong);
  48 static void     aunref(Aref*, ulong);
  49
  50 Block*
  51 allocb(int len)
  52 {
  53         int sz;
  54         Block *bp, **l;
  55
  56         len += PAD;
  57         sz = (len>>BPOW)&(NLIST-1);
  58
  59         qlock(&area);
  60         l = &area.list[sz];
  61         for(bp = *l; bp; bp = bp->flist) {
  62                 if(bp->bsz >= len) {
  63                         *l = bp->flist;
  64                         qunlock(&area);
  65
  66                         bp->next = nil;
  67                         bp->list = nil;
  68                         bp->flist = nil;
  69                         bp->base = (uchar*)bp+sizeof(Block);
  70                         bp->rptr = bp->base+PAD;
  71                         bp->wptr = bp->rptr;
  72                         bp->lim  = bp->base+bp->bsz;
  73                         bp->flow = nil;
  74                         bp->flags= 0;
  75                         ADEBUG {
  76                                 bp->pc = callerpc(&len);
  77                                 aref(&arefblock, bp->pc);
  78                         }
  79                         return bp;
  80                 }
  81                 l = &bp->flist;
  82         }
  83
  84         qunlock(&area);
  85
  86         bp = mallocz(sizeof(Block)+len, 1);
  87
  88         bp->bsz  = len;
  89         bp->base = (uchar*)bp+sizeof(Block);
  90         bp->rptr = bp->base+PAD;
  91         bp->wptr = bp->rptr;
  92         bp->lim  = bp->base+len;
  93         ADEBUG {
  94                 bp->pc = callerpc(&len);
  95                 aref(&arefblock, bp->pc);
  96         }
  97         return bp;
  98 }
  99
 100 void
 101 freeb(Block *bp)
 102 {
 103         int sz;
 104         Block **l, *next;
 105
 106         qlock(&area);
 107         while(bp) {
 108                 sz = (bp->bsz>>BPOW)&(NLIST-1);
 109
 110                 l = &area.list[sz];
 111                 bp->flist = *l;
 112                 *l = bp;
 113
 114                 next = bp->next;
 115
 116                 /* to catch use after free */
 117                 bp->rptr = (uchar*)0xdeadbabe;
 118                 bp->wptr = (uchar*)0xdeadbabe;
 119                 bp->next = (Block*)0xdeadbabe;
 120                 bp->list = (Block*)0xdeadbabe;
 121
 122                 ADEBUG aunref(&arefblock, bp->pc);
 123
 124                 bp = next;
 125         }
 126         qunlock(&area);
 127 }
 128
 129 /*
 130  *  concatenate a list of blocks into a single one and make sure
 131  *  the result is at least min uchars
 132  */
 133 Block*
 134 concat(Block *bp)
 135 {
 136         int len;
 137         Block *nb, *f;
 138
 139         nb = allocb(blen(bp));
 140         for(f = bp; f; f = f->next) {
 141                 len = BLEN(f);
 142                 memmove(nb->wptr, f->rptr, len);
 143                 nb->wptr += len;
 144         }
 145         freeb(bp);
 146         return nb;
 147 }
 148
 149 int
 150 blen(Block *bp)
 151 {
 152         int len;
 153
 154         len = 0;
 155         while(bp) {
 156                 len += BLEN(bp);
 157                 bp = bp->next;
 158         }
 159         return len;
 160 }
 161
 162 Block *
 163 pullup(Block *bp, int n)
 164 {
 165         int i;
 166         Block *nbp;
 167
 168         /*
 169          *  this should almost always be true, the rest it
 170          *  just for to avoid every caller checking.
 171          */
 172         if(BLEN(bp) >= n)
 173                 return bp;
 174
 175         /*
 176          *  if not enough room in the first block,
 177          *  add another to the front of the list.
 178          */
 179         if(bp->lim - bp->rptr < n){
 180                 nbp = allocb(n);
 181                 nbp->next = bp;
 182                 bp = nbp;
 183         }
 184
 185         /*
 186          *  copy uchars from the trailing blocks into the first
 187          */
 188         n -= BLEN(bp);
 189         while(nbp = bp->next){
 190                 i = BLEN(nbp);
 191                 if(i >= n) {
 192                         memmove(bp->wptr, nbp->rptr, n);
 193                         bp->wptr += n;
 194                         nbp->rptr += n;
 195                         return bp;
 196                 }
 197                 else {
 198                         memmove(bp->wptr, nbp->rptr, i);
 199                         bp->wptr += i;
 200                         bp->next = nbp->next;
 201                         nbp->next = nil;
 202                         freeb(nbp);
 203                         n -= i;
 204                 }
 205         }
 206         freeb(bp);
 207         return nil;
 208 }
 209
 210 /*
 211  *  Pad a block to the front with n uchars.  This is used to add protocol
 212  *  headers to the front of blocks.
 213  */
 214 Block*
 215 padb(Block *bp, int n)
 216 {
 217         Block *nbp;
 218
 219         if(bp->rptr-bp->base >= n) {
 220                 bp->rptr -= n;
 221                 return bp;
 222         }
 223         else {
 224                 /* fprint(2, "padb: required %d PAD %d\n", n, PAD) = malloc(sizeof(*required %d PAD %d\n", n, PAD))); */
 225                 nbp = allocb(n);
 226                 nbp->wptr = nbp->lim;
 227                 nbp->rptr = nbp->wptr - n;
 228                 nbp->next = bp;
 229                 return nbp;
 230         }
 231 }
 232
 233 Block *
 234 btrim(Block *bp, int offset, int len)
 235 {
 236         ulong l;
 237         Block *nb, *startb;
 238
 239         if(blen(bp) < offset+len) {
 240                 freeb(bp);
 241                 return nil;
 242         }
 243
 244         while((l = BLEN(bp)) < offset) {
 245                 offset -= l;
 246                 nb = bp->next;
 247                 bp->next = nil;
 248                 freeb(bp);
 249                 bp = nb;
 250         }
 251
 252         startb = bp;
 253         bp->rptr += offset;
 254
 255         while((l = BLEN(bp)) < len) {
 256                 len -= l;
 257                 bp = bp->next;
 258         }
 259
 260         bp->wptr -= (BLEN(bp) - len);
 261         bp->flags |= S_DELIM;
 262
 263         if(bp->next) {
 264                 freeb(bp->next);
 265                 bp->next = nil;
 266         }
 267
 268         return startb;
 269 }
 270
 271 Block*
 272 copyb(Block *bp, int count)
 273 {
 274         int l;
 275         Block *nb, *head, **p;
 276
 277         p = &head;
 278         head = nil;
 279         while(bp != nil && count != 0) {
 280                 l = BLEN(bp);
 281                 if(count < l)
 282                         l = count;
 283                 nb = allocb(l);
 284                 memmove(nb->wptr, bp->rptr, l);
 285                 nb->wptr += l;
 286                 count -= l;
 287                 nb->flags = bp->flags;
 288                 *p = nb;
 289                 p = &nb->next;
 290                 bp = bp->next;
 291         }
 292         if(count) {
 293                 nb = allocb(count);
 294                 memset(nb->wptr, 0, count);
 295                 nb->wptr += count;
 296                 nb->flags |= S_DELIM;
 297                 *p = nb;
 298         }
 299         if(blen(head) == 0)
 300                 fprint(2, "copyb: zero length\n");
 301
 302         return head;
 303 }
 304
 305 int
 306 pullb(Block **bph, int count)
 307 {
 308         Block *bp;
 309         int n, uchars;
 310
 311         uchars = 0;
 312         if(bph == nil)
 313                 return 0;
 314
 315         while(*bph != nil && count != 0) {
 316                 bp = *bph;
 317                 n = BLEN(bp);
 318                 if(count < n)
 319                         n = count;
 320                 uchars += n;
 321                 count -= n;
 322                 bp->rptr += n;
 323                 if(BLEN(bp) == 0) {
 324                         *bph = bp->next;
 325                         bp->next = nil;
 326                         freeb(bp);
 327                 }
 328         }
 329         return uchars;
 330 }
 331
 332 /*
 333  *  handy routines for keeping track of allocations
 334  */
 335 static ulong
 336 callerpc(void *a)
 337 {
 338         return ((ulong*)a)[-1];
 339 }
 340 static void
 341 aref(Aref *ap, ulong pc)
 342 {
 343         Arefent *a, *e;
 344
 345         e = &ap->tab[Npc-1];
 346         qlock(ap);
 347         for(a = ap->tab; a < e; a++)
 348                 if(a->pc == pc || a->pc == 0)
 349                         break;
 350         a->pc = pc;
 351         a->n++;
 352         qunlock(ap);
 353 }
 354 static void
 355 aunref(Aref *ap, ulong pc)
 356 {
 357         Arefent *a, *e;
 358
 359         e = &ap->tab[Npc-1];
 360         qlock(ap);
 361         for(a = ap->tab; a < e; a++)
 362                 if(a->pc == pc || a->pc == 0)
 363                         break;
 364         a->n--;
 365         qunlock(ap);
 366 }