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 Packet *p; /* parent packet, for debugging only */49 };51 struct Packet52 {53 int size;54 int asize; /* allocated memory - greater than size unless foreign frags */55 ulong pc;57 Packet *next;59 Frag *first;60 Frag *last;62 Frag local[NLocalFrag];63 };65 static Frag *fragalloc(Packet*, int n, int pos, Frag *next);66 static Frag *fragdup(Packet*, Frag*);67 static void fragfree(Frag*);69 static Mem *memalloc(int, int);70 static void memfree(Mem*);71 static int memhead(Mem *m, uchar *rp, int n);72 static int memtail(Mem *m, uchar *wp, int n);74 static char EPacketSize[] = "bad packet size";75 static char EPacketOffset[] = "bad packet offset";76 static char EBadSize[] = "bad size";78 static void checkpacket(Packet*);80 /*81 * the free list is primarily for speed, but it is82 * also necessary for packetsplit that packets83 * are never freed -- a packet can contain a different84 * packet's local fragments, thanks to packetsplit!85 */86 static struct {87 Lock lk;88 Packet *packet;89 int npacket;90 Frag *frag;91 int nfrag;92 Mem *bigmem;93 int nbigmem;94 Mem *smallmem;95 int nsmallmem;96 } freelist;98 #define FRAGSIZE(f) ((f)->wp - (f)->rp)99 #define FRAGASIZE(f) ((f)->mem ? (f)->mem->ep - (f)->mem->bp : 0)101 #define NOTFREE(p) assert((p)->size>=0)/*; checkpacket(p)*/103 Packet *104 packetalloc(void)105 {106 Packet *p;108 lock(&freelist.lk);109 p = freelist.packet;110 if(p != nil)111 freelist.packet = p->next;112 else113 freelist.npacket++;114 unlock(&freelist.lk);116 if(p == nil)117 p = vtbrk(sizeof(Packet));118 else119 assert(p->size == -1);120 p->size = 0;121 p->asize = 0;122 p->first = nil;123 p->last = nil;124 p->next = nil;125 p->pc = getcallerpc((char*)&p+8); /* might not work, but fine */127 //if(0)fprint(2, "packetalloc %p from %08lux %08lux %08lux\n", p, *((uint*)&p+2), *((uint*)&p+3), *((uint*)&p+4));129 NOTFREE(p);130 return p;131 }133 void134 packetfree(Packet *p)135 {136 Frag *f, *ff;138 //if(1)fprint(2, "packetfree %p from %08lux\n", p, getcallerpc(&p));140 if(p == nil)141 return;143 NOTFREE(p);144 p->pc = getcallerpc(&p);146 for(f=p->first; f!=nil; f=ff) {147 ff = f->next;148 fragfree(f);149 }150 p->first = (void*)0xDeadBeef;151 p->last = (void*)0xDeadBeef;152 p->size = -1;154 lock(&freelist.lk);155 p->next = freelist.packet;156 freelist.packet = p;157 unlock(&freelist.lk);158 }160 Packet *161 packetdup(Packet *p, int offset, int n)162 {163 Frag *f, *ff;164 Packet *pp;166 NOTFREE(p);167 if(offset < 0 || n < 0 || offset+n > p->size) {168 werrstr(EBadSize);169 return nil;170 }172 pp = packetalloc();173 pp->pc = getcallerpc(&p);174 if(n == 0){175 NOTFREE(pp);176 return pp;177 }179 pp->size = n;181 /* skip offset */182 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)183 offset -= FRAGSIZE(f);185 /* first frag */186 ff = fragdup(pp, f);187 ff->rp += offset;188 pp->first = ff;189 n -= FRAGSIZE(ff);190 pp->asize += FRAGASIZE(ff);192 /* the remaining */193 while(n > 0) {194 f = f->next;195 ff->next = fragdup(pp, f);196 ff = ff->next;197 n -= FRAGSIZE(ff);198 pp->asize += FRAGASIZE(ff);199 }201 /* fix up last frag: note n <= 0 */202 ff->wp += n;203 ff->next = nil;204 pp->last = ff;206 NOTFREE(pp);207 NOTFREE(p);208 return pp;209 }211 Packet *212 packetsplit(Packet *p, int n)213 {214 Packet *pp;215 Frag *f, *ff;217 if(0) fprint(2, "packetsplit %p %d\n", p, n);218 NOTFREE(p);219 if(n < 0 || n > p->size) {220 werrstr(EPacketSize);221 return nil;222 }224 pp = packetalloc();225 pp->pc = getcallerpc(&p);226 if(n == 0){227 NOTFREE(pp);228 return pp;229 }231 pp->size = n;232 p->size -= n;233 ff = nil;234 for(f=p->first; n > 0 && n >= FRAGSIZE(f); f=f->next) {235 n -= FRAGSIZE(f);236 p->asize -= FRAGASIZE(f);237 pp->asize += FRAGASIZE(f);238 f->p = pp;239 ff = f;240 }242 /* split shared frag */243 if(n > 0) {244 f->p = pp;245 ff = f;246 f = fragdup(p, ff);247 pp->asize += FRAGASIZE(ff);248 ff->wp = ff->rp + n;249 f->rp += n;250 }252 pp->first = p->first;253 pp->last = ff;254 ff->next = nil;255 p->first = f;256 if(f == nil || f->next == nil)257 p->last = f;258 NOTFREE(pp);259 NOTFREE(p);260 return pp;261 }263 int264 packetconsume(Packet *p, uchar *buf, int n)265 {266 if(0) fprint(2, "packetconsume %p %d\n", p, n);267 NOTFREE(p);268 if(buf && packetcopy(p, buf, 0, n) < 0)269 return -1;270 return packettrim(p, n, p->size-n);271 }273 int274 packettrim(Packet *p, int offset, int n)275 {276 Frag *f, *ff;278 if(0) fprint(2, "packettrim %p %d %d\n", p, offset, n);279 NOTFREE(p);280 if(offset < 0 || offset > p->size) {281 werrstr(EPacketOffset);282 return -1;283 }285 if(n < 0 || offset + n > p->size) {286 werrstr(EPacketOffset);287 return -1;288 }290 p->size = n;292 /* easy case */293 if(n == 0) {294 for(f=p->first; f != nil; f=ff) {295 ff = f->next;296 fragfree(f);297 }298 p->first = p->last = nil;299 p->asize = 0;300 NOTFREE(p);301 return 0;302 }304 /* free before offset */305 for(f=p->first; offset >= FRAGSIZE(f); f=ff) {306 p->asize -= FRAGASIZE(f);307 offset -= FRAGSIZE(f);308 ff = f->next;309 fragfree(f);310 }312 /* adjust frag */313 f->rp += offset;314 p->first = f;316 /* skip middle */317 for(; n > 0 && n > FRAGSIZE(f); f=f->next)318 n -= FRAGSIZE(f);320 /* adjust end */321 f->wp = f->rp + n;322 p->last = f;323 ff = f->next;324 f->next = nil;326 /* free after */327 for(f=ff; f != nil; f=ff) {328 p->asize -= FRAGASIZE(f);329 ff = f->next;330 fragfree(f);331 }332 NOTFREE(p);333 return 0;334 }336 uchar *337 packetheader(Packet *p, int n)338 {339 Frag *f;340 Mem *m;342 NOTFREE(p);343 if(n <= 0 || n > MaxFragSize) {344 werrstr(EPacketSize);345 return nil;346 }348 p->size += n;350 /* try and fix in current frag */351 f = p->first;352 if(f != nil) {353 m = f->mem;354 if(n <= f->rp - m->bp)355 if(m->ref == 1 || memhead(m, f->rp, n) >= 0) {356 f->rp -= n;357 NOTFREE(p);358 return f->rp;359 }360 }362 /* add frag to front */363 f = fragalloc(p, n, PEnd, p->first);364 p->asize += FRAGASIZE(f);365 if(p->first == nil)366 p->last = f;367 p->first = f;368 NOTFREE(p);369 return f->rp;370 }372 uchar *373 packettrailer(Packet *p, int n)374 {375 Mem *m;376 Frag *f;378 if(0) fprint(2, "packettrailer %p %d\n", p, n);379 NOTFREE(p);380 if(n <= 0 || n > MaxFragSize) {381 werrstr(EPacketSize);382 return nil;383 }385 p->size += n;387 /* try and fix in current frag */388 if(p->first != nil) {389 f = p->last;390 m = f->mem;391 if(n <= m->ep - f->wp)392 if(m->ref == 1 || memtail(m, f->wp, n) >= 0) {393 f->wp += n;394 NOTFREE(p);395 return f->wp - n;396 }397 }399 /* add frag to end */400 f = fragalloc(p, n, (p->first == nil)?PMiddle:PFront, nil);401 p->asize += FRAGASIZE(f);402 if(p->first == nil)403 p->first = f;404 else405 p->last->next = f;406 p->last = f;407 NOTFREE(p);408 return f->rp;409 }411 void412 packetprefix(Packet *p, uchar *buf, int n)413 {414 Frag *f;415 int nn;416 Mem *m;418 NOTFREE(p);419 if(n <= 0)420 return;422 p->size += n;424 /* try and fix in current frag */425 f = p->first;426 if(f != nil) {427 m = f->mem;428 nn = f->rp - m->bp;429 if(nn > n)430 nn = n;431 if(m->ref == 1 || memhead(m, f->rp, nn) >= 0) {432 f->rp -= nn;433 n -= nn;434 memmove(f->rp, buf+n, nn);435 }436 }438 while(n > 0) {439 nn = n;440 if(nn > MaxFragSize)441 nn = MaxFragSize;442 f = fragalloc(p, nn, PEnd, p->first);443 p->asize += FRAGASIZE(f);444 if(p->first == nil)445 p->last = f;446 p->first = f;447 n -= nn;448 memmove(f->rp, buf+n, nn);449 }450 NOTFREE(p);451 }453 void454 packetappend(Packet *p, uchar *buf, int n)455 {456 Frag *f;457 int nn;458 Mem *m;460 NOTFREE(p);461 if(n <= 0)462 return;464 p->size += n;465 /* try and fix in current frag */466 if(p->first != nil) {467 f = p->last;468 m = f->mem;469 nn = m->ep - f->wp;470 if(nn > n)471 nn = n;472 if(m->ref == 1 || memtail(m, f->wp, nn) >= 0) {473 memmove(f->wp, buf, nn);474 f->wp += nn;475 buf += nn;476 n -= nn;477 }478 }480 while(n > 0) {481 nn = n;482 if(nn > MaxFragSize)483 nn = MaxFragSize;484 f = fragalloc(p, nn, (p->first == nil)?PMiddle:PFront, nil);485 p->asize += FRAGASIZE(f);486 if(p->first == nil)487 p->first = f;488 else489 p->last->next = f;490 p->last = f;491 memmove(f->rp, buf, nn);492 buf += nn;493 n -= nn;494 }495 NOTFREE(p);496 }498 void499 packetconcat(Packet *p, Packet *pp)500 {501 Frag *f;503 NOTFREE(p);504 NOTFREE(pp);505 if(pp->size == 0)506 return;507 p->size += pp->size;508 p->asize += pp->asize;509 for(f=pp->first; f; f=f->next)510 f->p = p;512 if(p->first != nil)513 p->last->next = pp->first;514 else515 p->first = pp->first;517 p->last = pp->last;518 pp->size = 0;519 pp->asize = 0;520 pp->first = nil;521 pp->last = nil;522 NOTFREE(p);523 NOTFREE(pp);524 }526 uchar *527 packetpeek(Packet *p, uchar *buf, int offset, int n)528 {529 Frag *f;530 int nn;531 uchar *b;533 NOTFREE(p);534 if(n == 0)535 return buf;537 if(offset < 0 || offset >= p->size) {538 werrstr(EPacketOffset);539 return nil;540 }542 if(n < 0 || offset + n > p->size) {543 werrstr(EPacketSize);544 return nil;545 }547 /* skip up to offset */548 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)549 offset -= FRAGSIZE(f);551 /* easy case */552 if(offset + n <= FRAGSIZE(f)){553 NOTFREE(p);554 return f->rp + offset;555 }557 for(b=buf; n>0; n -= nn) {558 nn = FRAGSIZE(f) - offset;559 if(nn > n)560 nn = n;561 memmove(b, f->rp+offset, nn);562 offset = 0;563 f = f->next;564 b += nn;565 }567 NOTFREE(p);568 return buf;569 }571 int572 packetcopy(Packet *p, uchar *buf, int offset, int n)573 {574 uchar *b;576 NOTFREE(p);577 b = packetpeek(p, buf, offset, n);578 if(b == nil)579 return -1;580 if(b != buf)581 memmove(buf, b, n);582 return 0;583 }585 int586 packetfragments(Packet *p, IOchunk *io, int nio, int offset)587 {588 Frag *f;589 int size;590 IOchunk *eio;592 NOTFREE(p);593 if(p->size == 0 || nio <= 0)594 return 0;596 if(offset < 0 || offset > p->size) {597 werrstr(EPacketOffset);598 return -1;599 }601 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)602 offset -= FRAGSIZE(f);604 size = 0;605 eio = io + nio;606 for(; f != nil && io < eio; f=f->next) {607 io->addr = f->rp + offset;608 io->len = f->wp - (f->rp + offset);609 offset = 0;610 size += io->len;611 io++;612 }614 return size;615 }617 void618 packetstats(void)619 {620 Packet *p;621 Frag *f;622 Mem *m;624 int np, nf, nsm, nbm;626 lock(&freelist.lk);627 np = 0;628 for(p=freelist.packet; p; p=p->next)629 np++;630 nf = 0;631 for(f=freelist.frag; f; f=f->next)632 nf++;633 nsm = 0;634 for(m=freelist.smallmem; m; m=m->next)635 nsm++;636 nbm = 0;637 for(m=freelist.bigmem; m; m=m->next)638 nbm++;640 fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",641 np, freelist.npacket,642 nf, freelist.nfrag,643 nsm, freelist.nsmallmem,644 nbm, freelist.nbigmem);646 unlock(&freelist.lk);647 }650 uint651 packetsize(Packet *p)652 {653 NOTFREE(p);654 if(1) {655 Frag *f;656 int size = 0;658 for(f=p->first; f; f=f->next)659 size += FRAGSIZE(f);660 if(size != p->size)661 fprint(2, "packetsize %d %d\n", size, p->size);662 assert(size == p->size);663 }664 return p->size;665 }667 uint668 packetasize(Packet *p)669 {670 NOTFREE(p);671 if(0) {672 Frag *f;673 int asize = 0;675 for(f=p->first; f; f=f->next)676 asize += FRAGASIZE(f);677 if(asize != p->asize)678 fprint(2, "packetasize %d %d\n", asize, p->asize);679 assert(asize == p->asize);680 }681 return p->asize;682 }684 void685 packetsha1(Packet *p, uchar digest[VtScoreSize])686 {687 DigestState ds;688 Frag *f;689 int size;691 NOTFREE(p);692 memset(&ds, 0, sizeof ds);693 size = p->size;694 for(f=p->first; f; f=f->next) {695 sha1(f->rp, FRAGSIZE(f), nil, &ds);696 size -= FRAGSIZE(f);697 }698 assert(size == 0);699 sha1(nil, 0, digest, &ds);700 }702 int703 packetcmp(Packet *pkt0, Packet *pkt1)704 {705 Frag *f0, *f1;706 int n0, n1, x;708 NOTFREE(pkt0);709 NOTFREE(pkt1);710 f0 = pkt0->first;711 f1 = pkt1->first;713 if(f0 == nil)714 return (f1 == nil)?0:-1;715 if(f1 == nil)716 return 1;717 n0 = FRAGSIZE(f0);718 n1 = FRAGSIZE(f1);720 for(;;) {721 if(n0 < n1) {722 x = memcmp(f0->wp - n0, f1->wp - n1, n0);723 if(x != 0)724 return x;725 n1 -= n0;726 f0 = f0->next;727 if(f0 == nil)728 return -1;729 n0 = FRAGSIZE(f0);730 } else if (n0 > n1) {731 x = memcmp(f0->wp - n0, f1->wp - n1, n1);732 if(x != 0)733 return x;734 n0 -= n1;735 f1 = f1->next;736 if(f1 == nil)737 return 1;738 n1 = FRAGSIZE(f1);739 } else { /* n0 == n1 */740 x = memcmp(f0->wp - n0, f1->wp - n1, n0);741 if(x != 0)742 return x;743 f0 = f0->next;744 f1 = f1->next;745 if(f0 == nil)746 return (f1 == nil)?0:-1;747 if(f1 == nil)748 return 1;749 n0 = FRAGSIZE(f0);750 n1 = FRAGSIZE(f1);751 }752 }753 return 0; /* for ken */754 }757 static Frag *758 fragalloc(Packet *p, int n, int pos, Frag *next)759 {760 Frag *f, *ef;761 Mem *m;763 /* look for local frag */764 f = &p->local[0];765 ef = &p->local[NLocalFrag];766 for(;f<ef; f++) {767 if(f->state == FragLocalFree) {768 f->state = FragLocalAlloc;769 goto Found;770 }771 }772 lock(&freelist.lk);773 f = freelist.frag;774 if(f != nil)775 freelist.frag = f->next;776 else777 freelist.nfrag++;778 unlock(&freelist.lk);780 if(f == nil) {781 f = vtbrk(sizeof(Frag));782 f->state = FragGlobal;783 }785 Found:786 f->next = next;787 f->p = p;789 if(n == 0){790 f->mem = 0;791 f->rp = 0;792 f->wp = 0;793 return f;794 }796 if(pos == PEnd && next == nil)797 pos = PMiddle;798 m = memalloc(n, pos);799 f->mem = m;800 f->rp = m->rp;801 f->wp = m->wp;802 return f;803 }805 Packet*806 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)807 {808 Packet *p;809 Frag *f;811 p = packetalloc();812 p->pc = getcallerpc(&buf);813 f = fragalloc(p, 0, 0, nil);814 f->free = free;815 f->a = a;816 f->next = nil;817 f->rp = buf;818 f->wp = buf+n;820 p->first = f;821 p->last = f;822 p->size = n;823 NOTFREE(p);824 return p;825 }827 static Frag *828 fragdup(Packet *p, Frag *f)829 {830 Frag *ff;831 Mem *m;833 m = f->mem;835 /*836 * m->rp && m->wp can be out of date when ref == 1837 * also, potentially reclaims space from previous frags838 */839 if(m && m->ref == 1) {840 m->rp = f->rp;841 m->wp = f->wp;842 }844 ff = fragalloc(p, 0, 0, nil);845 ff->mem = f->mem;846 ff->rp = f->rp;847 ff->wp = f->wp;848 ff->next = f->next;850 /*851 * We can't duplicate these -- there's no dup function.852 */853 assert(f->free==nil && f->a==nil);855 if(m){856 lock(&m->lk);857 m->ref++;858 unlock(&m->lk);859 }862 return ff;863 }866 static void867 fragfree(Frag *f)868 {869 if(f->mem == nil){870 if(f->free)871 (*f->free)(f->a);872 }else{873 memfree(f->mem);874 f->mem = 0;875 }877 if(f->state == FragLocalAlloc) {878 f->state = FragLocalFree;879 return;880 }882 lock(&freelist.lk);883 f->next = freelist.frag;884 freelist.frag = f;885 unlock(&freelist.lk);886 }888 static Mem *889 memalloc(int n, int pos)890 {891 Mem *m;892 int nn;894 if(n < 0 || n > MaxFragSize) {895 werrstr(EPacketSize);896 return 0;897 }898 if(n <= SmallMemSize) {899 lock(&freelist.lk);900 m = freelist.smallmem;901 if(m != nil)902 freelist.smallmem = m->next;903 else904 freelist.nsmallmem++;905 unlock(&freelist.lk);906 nn = SmallMemSize;907 } else {908 lock(&freelist.lk);909 m = freelist.bigmem;910 if(m != nil)911 freelist.bigmem = m->next;912 else913 freelist.nbigmem++;914 unlock(&freelist.lk);915 nn = BigMemSize;916 }918 if(m == nil) {919 m = vtbrk(sizeof(Mem));920 m->bp = vtbrk(nn);921 m->ep = m->bp + nn;922 }923 assert(m->ref == 0);924 m->ref = 1;926 switch(pos) {927 default:928 assert(0);929 case PFront:930 m->rp = m->bp;931 break;932 case PMiddle:933 /* leave a little bit at end */934 m->rp = m->ep - n - 32;935 break;936 case PEnd:937 m->rp = m->ep - n;938 break;939 }940 /* check we did not blow it */941 if(m->rp < m->bp)942 m->rp = m->bp;943 m->wp = m->rp + n;944 assert(m->rp >= m->bp && m->wp <= m->ep);945 return m;946 }948 static void949 memfree(Mem *m)950 {951 lock(&m->lk);952 m->ref--;953 if(m->ref > 0) {954 unlock(&m->lk);955 return;956 }957 unlock(&m->lk);958 assert(m->ref == 0);960 /* memset(m->bp, 0xEF, m->ep-m->bp); */961 switch(m->ep - m->bp) {962 default:963 assert(0);964 case SmallMemSize:965 lock(&freelist.lk);966 m->next = freelist.smallmem;967 freelist.smallmem = m;968 unlock(&freelist.lk);969 break;970 case BigMemSize:971 lock(&freelist.lk);972 m->next = freelist.bigmem;973 freelist.bigmem = m;974 unlock(&freelist.lk);975 break;976 }977 }979 static int980 memhead(Mem *m, uchar *rp, int n)981 {982 fprint(2, "memhead called\n");983 abort();984 lock(&m->lk);985 if(m->rp != rp) {986 unlock(&m->lk);987 return -1;988 }989 m->rp -= n;990 unlock(&m->lk);991 return 0;992 }994 static int995 memtail(Mem *m, uchar *wp, int n)996 {997 fprint(2, "memtail called\n");998 abort();999 lock(&m->lk);1000 if(m->wp != wp) {1001 unlock(&m->lk);1002 return -1;1003 }1004 m->wp += n;1005 unlock(&m->lk);1006 return 0;1007 }1009 static void1010 checkpacket(Packet *p)1011 {1012 int s, as;1013 Frag *f;1014 Frag *ff;1016 s = 0;1017 as = 0;1018 ff=p->first;1019 for(f=p->first; f; ff=f,f=f->next){1020 assert(f->p == p);1021 s += FRAGSIZE(f);1022 as += FRAGASIZE(f);1023 }1024 assert(s == p->size);1025 assert(as == p->asize);1026 if(p->first)1027 assert(ff==p->last);1028 }