Blob
1 #include <u.h>2 #include <libc.h>3 #include <venti.h>4 #include <libsec.h>6 typedef struct Mem Mem;7 typedef struct Frag Frag;9 enum {10 BigMemSize = MaxFragSize,11 SmallMemSize = BigMemSize/8,12 NLocalFrag = 2,13 };15 /* position to carve out of a Mem */16 enum {17 PFront,18 PMiddle,19 PEnd,20 };22 struct Mem23 {24 Lock lk;25 int ref;26 uchar *bp;27 uchar *ep;28 uchar *rp;29 uchar *wp;30 Mem *next;31 };33 enum {34 FragLocalFree,35 FragLocalAlloc,36 FragGlobal,37 };39 struct Frag40 {41 int state;42 Mem *mem;43 uchar *rp;44 uchar *wp;45 Frag *next;46 void (*free)(void*);47 void *a;48 };50 struct Packet51 {52 int size;53 int asize; /* allocated memory - greater than size unless foreign frags */55 Packet *next;57 Frag *first;58 Frag *last;60 Frag local[NLocalFrag];61 };63 static Frag *fragalloc(Packet*, int n, int pos, Frag *next);64 static Frag *fragdup(Packet*, Frag*);65 static void fragfree(Frag*);67 static Mem *memalloc(int, int);68 static void memfree(Mem*);69 static int memhead(Mem *m, uchar *rp, int n);70 static int memtail(Mem *m, uchar *wp, int n);72 static char EPacketSize[] = "bad packet size";73 static char EPacketOffset[] = "bad packet offset";74 static char EBadSize[] = "bad size";76 static struct {77 Lock lk;78 Packet *packet;79 int npacket;80 Frag *frag;81 int nfrag;82 Mem *bigmem;83 int nbigmem;84 Mem *smallmem;85 int nsmallmem;86 } freelist;88 #define FRAGSIZE(f) ((f)->wp - (f)->rp)89 #define FRAGASIZE(f) ((f)->mem ? (f)->mem->ep - (f)->mem->bp : 0)91 #define NOTFREE(p) assert((p)->size>=0)93 Packet *94 packetalloc(void)95 {96 Packet *p;98 lock(&freelist.lk);99 p = freelist.packet;100 if(p != nil)101 freelist.packet = p->next;102 else103 freelist.npacket++;104 unlock(&freelist.lk);106 if(p == nil)107 p = vtbrk(sizeof(Packet));108 else109 assert(p->size == -1);110 p->size = 0;111 p->asize = 0;112 p->first = nil;113 p->last = nil;114 p->next = nil;116 if(0)fprint(2, "packetalloc %p from %08lux %08lux %08lux\n", p, *((uint*)&p+2), *((uint*)&p+3), *((uint*)&p+4));118 return p;119 }121 void122 packetfree(Packet *p)123 {124 Frag *f, *ff;126 if(0)fprint(2, "packetfree %p from %08lux\n", p, getcallerpc(&p));128 if(p == nil)129 return;131 NOTFREE(p);132 p->size = -1;134 for(f=p->first; f!=nil; f=ff) {135 ff = f->next;136 fragfree(f);137 }138 p->first = nil;139 p->last = nil;141 lock(&freelist.lk);142 p->next = freelist.packet;143 freelist.packet = p;144 unlock(&freelist.lk);145 }147 Packet *148 packetdup(Packet *p, int offset, int n)149 {150 Frag *f, *ff;151 Packet *pp;153 NOTFREE(p);154 if(offset < 0 || n < 0 || offset+n > p->size) {155 werrstr(EBadSize);156 return nil;157 }159 pp = packetalloc();160 if(n == 0)161 return pp;163 pp->size = n;165 /* skip offset */166 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)167 offset -= FRAGSIZE(f);169 /* first frag */170 ff = fragdup(pp, f);171 ff->rp += offset;172 pp->first = ff;173 n -= FRAGSIZE(ff);174 pp->asize += FRAGASIZE(ff);176 /* the remaining */177 while(n > 0) {178 f = f->next;179 ff->next = fragdup(pp, f);180 ff = ff->next;181 n -= FRAGSIZE(ff);182 pp->asize += FRAGASIZE(ff);183 }185 /* fix up last frag: note n <= 0 */186 ff->wp += n;187 ff->next = nil;188 pp->last = ff;190 return pp;191 }193 Packet *194 packetsplit(Packet *p, int n)195 {196 Packet *pp;197 Frag *f, *ff;199 NOTFREE(p);200 if(n < 0 || n > p->size) {201 werrstr(EPacketSize);202 return nil;203 }205 pp = packetalloc();206 if(n == 0)207 return pp;209 pp->size = n;210 p->size -= n;211 ff = nil;212 for(f=p->first; n > 0 && n >= FRAGSIZE(f); f=f->next) {213 n -= FRAGSIZE(f);214 p->asize -= FRAGASIZE(f);215 pp->asize += FRAGASIZE(f);216 ff = f;217 }219 /* split shared frag */220 if(n > 0) {221 ff = f;222 f = fragdup(pp, ff);223 pp->asize += FRAGASIZE(ff);224 ff->next = nil;225 ff->wp = ff->rp + n;226 f->rp += n;227 }229 pp->first = p->first;230 pp->last = ff;231 p->first = f;232 return pp;233 }235 int236 packetconsume(Packet *p, uchar *buf, int n)237 {238 NOTFREE(p);239 if(buf && packetcopy(p, buf, 0, n) < 0)240 return -1;241 return packettrim(p, n, p->size-n);242 }244 int245 packettrim(Packet *p, int offset, int n)246 {247 Frag *f, *ff;249 NOTFREE(p);250 if(offset < 0 || offset > p->size) {251 werrstr(EPacketOffset);252 return -1;253 }255 if(n < 0 || offset + n > p->size) {256 werrstr(EPacketOffset);257 return -1;258 }260 p->size = n;262 /* easy case */263 if(n == 0) {264 for(f=p->first; f != nil; f=ff) {265 ff = f->next;266 fragfree(f);267 }268 p->first = p->last = nil;269 p->asize = 0;270 return 0;271 }273 /* free before offset */274 for(f=p->first; offset >= FRAGSIZE(f); f=ff) {275 p->asize -= FRAGASIZE(f);276 offset -= FRAGSIZE(f);277 ff = f->next;278 fragfree(f);279 }281 /* adjust frag */282 f->rp += offset;283 p->first = f;285 /* skip middle */286 for(; n > 0 && n > FRAGSIZE(f); f=f->next)287 n -= FRAGSIZE(f);289 /* adjust end */290 f->wp = f->rp + n;291 p->last = f;292 ff = f->next;293 f->next = nil;295 /* free after */296 for(f=ff; f != nil; f=ff) {297 p->asize -= FRAGASIZE(f);298 ff = f->next;299 fragfree(f);300 }301 return 0;302 }304 uchar *305 packetheader(Packet *p, int n)306 {307 Frag *f;308 Mem *m;310 NOTFREE(p);311 if(n <= 0 || n > MaxFragSize) {312 werrstr(EPacketSize);313 return nil;314 }316 p->size += n;318 /* try and fix in current frag */319 f = p->first;320 if(f != nil) {321 m = f->mem;322 if(n <= f->rp - m->bp)323 if(m->ref == 1 || memhead(m, f->rp, n) >= 0) {324 f->rp -= n;325 return f->rp;326 }327 }329 /* add frag to front */330 f = fragalloc(p, n, PEnd, p->first);331 p->asize += FRAGASIZE(f);332 if(p->first == nil)333 p->last = f;334 p->first = f;335 return f->rp;336 }338 uchar *339 packettrailer(Packet *p, int n)340 {341 Mem *m;342 Frag *f;344 NOTFREE(p);345 if(n <= 0 || n > MaxFragSize) {346 werrstr(EPacketSize);347 return nil;348 }350 p->size += n;352 /* try and fix in current frag */353 if(p->first != nil) {354 f = p->last;355 m = f->mem;356 if(n <= m->ep - f->wp)357 if(m->ref == 1 || memtail(m, f->wp, n) >= 0) {358 f->wp += n;359 return f->wp - n;360 }361 }363 /* add frag to end */364 f = fragalloc(p, n, (p->first == nil)?PMiddle:PFront, nil);365 p->asize += FRAGASIZE(f);366 if(p->first == nil)367 p->first = f;368 else369 p->last->next = f;370 p->last = f;371 return f->rp;372 }374 void375 packetprefix(Packet *p, uchar *buf, int n)376 {377 Frag *f;378 int nn;379 Mem *m;381 NOTFREE(p);382 if(n <= 0)383 return;385 p->size += n;387 /* try and fix in current frag */388 f = p->first;389 if(f != nil) {390 m = f->mem;391 nn = f->rp - m->bp;392 if(nn > n)393 nn = n;394 if(m->ref == 1 || memhead(m, f->rp, nn) >= 0) {395 f->rp -= nn;396 n -= nn;397 memmove(f->rp, buf+n, nn);398 }399 }401 while(n > 0) {402 nn = n;403 if(nn > MaxFragSize)404 nn = MaxFragSize;405 f = fragalloc(p, nn, PEnd, p->first);406 p->asize += FRAGASIZE(f);407 if(p->first == nil)408 p->last = f;409 p->first = f;410 n -= nn;411 memmove(f->rp, buf+n, nn);412 }413 }415 void416 packetappend(Packet *p, uchar *buf, int n)417 {418 Frag *f;419 int nn;420 Mem *m;422 NOTFREE(p);423 if(n <= 0)424 return;426 p->size += n;427 /* try and fix in current frag */428 if(p->first != nil) {429 f = p->last;430 m = f->mem;431 nn = m->ep - f->wp;432 if(nn > n)433 nn = n;434 if(m->ref == 1 || memtail(m, f->wp, nn) >= 0) {435 memmove(f->wp, buf, nn);436 f->wp += nn;437 buf += nn;438 n -= nn;439 }440 }442 while(n > 0) {443 nn = n;444 if(nn > MaxFragSize)445 nn = MaxFragSize;446 f = fragalloc(p, nn, (p->first == nil)?PMiddle:PFront, nil);447 p->asize += FRAGASIZE(f);448 if(p->first == nil)449 p->first = f;450 else451 p->last->next = f;452 p->last = f;453 memmove(f->rp, buf, nn);454 buf += nn;455 n -= nn;456 }457 return;458 }460 void461 packetconcat(Packet *p, Packet *pp)462 {463 NOTFREE(p);464 NOTFREE(pp);465 if(pp->size == 0)466 return;467 p->size += pp->size;468 p->asize += pp->asize;470 if(p->first != nil)471 p->last->next = pp->first;472 else473 p->first = pp->first;474 p->last = pp->last;475 pp->size = 0;476 pp->asize = 0;477 pp->first = nil;478 pp->last = nil;479 }481 uchar *482 packetpeek(Packet *p, uchar *buf, int offset, int n)483 {484 Frag *f;485 int nn;486 uchar *b;488 NOTFREE(p);489 if(n == 0)490 return buf;492 if(offset < 0 || offset >= p->size) {493 werrstr(EPacketOffset);494 return nil;495 }497 if(n < 0 || offset + n > p->size) {498 werrstr(EPacketSize);499 return nil;500 }502 /* skip up to offset */503 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)504 offset -= FRAGSIZE(f);506 /* easy case */507 if(offset + n <= FRAGSIZE(f))508 return f->rp + offset;510 for(b=buf; n>0; n -= nn) {511 nn = FRAGSIZE(f) - offset;512 if(nn > n)513 nn = n;514 memmove(b, f->rp+offset, nn);515 offset = 0;516 f = f->next;517 b += nn;518 }520 return buf;521 }523 int524 packetcopy(Packet *p, uchar *buf, int offset, int n)525 {526 uchar *b;528 NOTFREE(p);529 b = packetpeek(p, buf, offset, n);530 if(b == nil)531 return -1;532 if(b != buf)533 memmove(buf, b, n);534 return 0;535 }537 int538 packetfragments(Packet *p, IOchunk *io, int nio, int offset)539 {540 Frag *f;541 int size;542 IOchunk *eio;544 NOTFREE(p);545 if(p->size == 0 || nio <= 0)546 return 0;548 if(offset < 0 || offset > p->size) {549 werrstr(EPacketOffset);550 return -1;551 }553 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)554 offset -= FRAGSIZE(f);556 size = 0;557 eio = io + nio;558 for(; f != nil && io < eio; f=f->next) {559 io->addr = f->rp + offset;560 io->len = f->wp - (f->rp + offset);561 offset = 0;562 size += io->len;563 io++;564 }566 return size;567 }569 void570 packetstats(void)571 {572 Packet *p;573 Frag *f;574 Mem *m;576 int np, nf, nsm, nbm;578 lock(&freelist.lk);579 np = 0;580 for(p=freelist.packet; p; p=p->next)581 np++;582 nf = 0;583 for(f=freelist.frag; f; f=f->next)584 nf++;585 nsm = 0;586 for(m=freelist.smallmem; m; m=m->next)587 nsm++;588 nbm = 0;589 for(m=freelist.bigmem; m; m=m->next)590 nbm++;592 fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",593 np, freelist.npacket,594 nf, freelist.nfrag,595 nsm, freelist.nsmallmem,596 nbm, freelist.nbigmem);598 unlock(&freelist.lk);599 }602 uint603 packetsize(Packet *p)604 {605 NOTFREE(p);606 if(0) {607 Frag *f;608 int size = 0;610 for(f=p->first; f; f=f->next)611 size += FRAGSIZE(f);612 if(size != p->size)613 fprint(2, "packetsize %d %d\n", size, p->size);614 assert(size == p->size);615 }616 return p->size;617 }619 uint620 packetasize(Packet *p)621 {622 NOTFREE(p);623 if(0) {624 Frag *f;625 int asize = 0;627 for(f=p->first; f; f=f->next)628 asize += FRAGASIZE(f);629 if(asize != p->asize)630 fprint(2, "packetasize %d %d\n", asize, p->asize);631 assert(asize == p->asize);632 }633 return p->asize;634 }636 void637 packetsha1(Packet *p, uchar digest[VtScoreSize])638 {639 DigestState ds;640 Frag *f;641 int size;643 NOTFREE(p);644 memset(&ds, 0, sizeof ds);645 size = p->size;646 for(f=p->first; f; f=f->next) {647 sha1(f->rp, FRAGSIZE(f), nil, &ds);648 size -= FRAGSIZE(f);649 }650 assert(size == 0);651 sha1(nil, 0, digest, &ds);652 }654 int655 packetcmp(Packet *pkt0, Packet *pkt1)656 {657 Frag *f0, *f1;658 int n0, n1, x;660 NOTFREE(pkt0);661 NOTFREE(pkt1);662 f0 = pkt0->first;663 f1 = pkt1->first;665 if(f0 == nil)666 return (f1 == nil)?0:-1;667 if(f1 == nil)668 return 1;669 n0 = FRAGSIZE(f0);670 n1 = FRAGSIZE(f1);672 for(;;) {673 if(n0 < n1) {674 x = memcmp(f0->wp - n0, f1->wp - n1, n0);675 if(x != 0)676 return x;677 n1 -= n0;678 f0 = f0->next;679 if(f0 == nil)680 return -1;681 n0 = FRAGSIZE(f0);682 } else if (n0 > n1) {683 x = memcmp(f0->wp - n0, f1->wp - n1, n1);684 if(x != 0)685 return x;686 n0 -= n1;687 f1 = f1->next;688 if(f1 == nil)689 return 1;690 n1 = FRAGSIZE(f1);691 } else { /* n0 == n1 */692 x = memcmp(f0->wp - n0, f1->wp - n1, n0);693 if(x != 0)694 return x;695 f0 = f0->next;696 f1 = f1->next;697 if(f0 == nil)698 return (f1 == nil)?0:-1;699 if(f1 == nil)700 return 1;701 n0 = FRAGSIZE(f0);702 n1 = FRAGSIZE(f1);703 }704 }705 return 0; /* for ken */706 }709 static Frag *710 fragalloc(Packet *p, int n, int pos, Frag *next)711 {712 Frag *f, *ef;713 Mem *m;715 /* look for local frag */716 f = &p->local[0];717 ef = &p->local[NLocalFrag];718 for(;f<ef; f++) {719 if(f->state == FragLocalFree) {720 f->state = FragLocalAlloc;721 goto Found;722 }723 }724 lock(&freelist.lk);725 f = freelist.frag;726 if(f != nil)727 freelist.frag = f->next;728 else729 freelist.nfrag++;730 unlock(&freelist.lk);732 if(f == nil) {733 f = vtbrk(sizeof(Frag));734 f->state = FragGlobal;735 }737 Found:738 f->next = next;740 if(n == 0){741 f->mem = 0;742 f->rp = 0;743 f->wp = 0;744 return f;745 }747 if(pos == PEnd && next == nil)748 pos = PMiddle;749 m = memalloc(n, pos);750 f->mem = m;751 f->rp = m->rp;752 f->wp = m->wp;753 return f;754 }756 Packet*757 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)758 {759 Packet *p;760 Frag *f;762 p = packetalloc();763 f = fragalloc(p, 0, 0, nil);764 f->free = free;765 f->a = a;766 f->next = nil;767 f->rp = buf;768 f->wp = buf+n;770 p->first = f;771 p->size = n;772 return p;773 }775 static Frag *776 fragdup(Packet *p, Frag *f)777 {778 Frag *ff;779 Mem *m;781 m = f->mem;783 /*784 * m->rp && m->wp can be out of date when ref == 1785 * also, potentially reclaims space from previous frags786 */787 if(m && m->ref == 1) {788 m->rp = f->rp;789 m->wp = f->wp;790 }792 ff = fragalloc(p, 0, 0, nil);793 *ff = *f;794 if(m){795 lock(&m->lk);796 m->ref++;797 unlock(&m->lk);798 }799 return ff;800 }803 static void804 fragfree(Frag *f)805 {806 if(f->mem == nil){807 if(f->free)808 (*f->free)(f->a);809 }else{810 memfree(f->mem);811 f->mem = 0;812 }814 if(f->state == FragLocalAlloc) {815 f->state = FragLocalFree;816 return;817 }819 lock(&freelist.lk);820 f->next = freelist.frag;821 freelist.frag = f;822 unlock(&freelist.lk);823 }825 static Mem *826 memalloc(int n, int pos)827 {828 Mem *m;829 int nn;831 if(n < 0 || n > MaxFragSize) {832 werrstr(EPacketSize);833 return 0;834 }835 if(n <= SmallMemSize) {836 lock(&freelist.lk);837 m = freelist.smallmem;838 if(m != nil)839 freelist.smallmem = m->next;840 else841 freelist.nsmallmem++;842 unlock(&freelist.lk);843 nn = SmallMemSize;844 } else {845 lock(&freelist.lk);846 m = freelist.bigmem;847 if(m != nil)848 freelist.bigmem = m->next;849 else850 freelist.nbigmem++;851 unlock(&freelist.lk);852 nn = BigMemSize;853 }855 if(m == nil) {856 m = vtbrk(sizeof(Mem));857 m->bp = vtbrk(nn);858 m->ep = m->bp + nn;859 }860 assert(m->ref == 0);861 m->ref = 1;863 switch(pos) {864 default:865 assert(0);866 case PFront:867 m->rp = m->bp;868 break;869 case PMiddle:870 /* leave a little bit at end */871 m->rp = m->ep - n - 32;872 break;873 case PEnd:874 m->rp = m->ep - n;875 break;876 }877 /* check we did not blow it */878 if(m->rp < m->bp)879 m->rp = m->bp;880 m->wp = m->rp + n;881 assert(m->rp >= m->bp && m->wp <= m->ep);882 return m;883 }885 static void886 memfree(Mem *m)887 {888 lock(&m->lk);889 m->ref--;890 if(m->ref > 0) {891 unlock(&m->lk);892 return;893 }894 unlock(&m->lk);895 assert(m->ref == 0);897 switch(m->ep - m->bp) {898 default:899 assert(0);900 case SmallMemSize:901 lock(&freelist.lk);902 m->next = freelist.smallmem;903 freelist.smallmem = m;904 unlock(&freelist.lk);905 break;906 case BigMemSize:907 lock(&freelist.lk);908 m->next = freelist.bigmem;909 freelist.bigmem = m;910 unlock(&freelist.lk);911 break;912 }913 }915 static int916 memhead(Mem *m, uchar *rp, int n)917 {918 lock(&m->lk);919 if(m->rp != rp) {920 unlock(&m->lk);921 return -1;922 }923 m->rp -= n;924 unlock(&m->lk);925 return 0;926 }928 static int929 memtail(Mem *m, uchar *wp, int n)930 {931 lock(&m->lk);932 if(m->wp != wp) {933 unlock(&m->lk);934 return -1;935 }936 m->wp += n;937 unlock(&m->lk);938 return 0;939 }