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 = 213 };15 /* position to carve out of a Mem */16 enum {17 PFront,18 PMiddle,19 PEnd20 };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 FragGlobal37 };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 #ifdef NOTDEF79 static void checkpacket(Packet*);80 #endif82 /*83 * the free list is primarily for speed, but it is84 * also necessary for packetsplit that packets85 * are never freed -- a packet can contain a different86 * packet's local fragments, thanks to packetsplit!87 */88 static struct {89 Lock lk;90 Packet *packet;91 int npacket;92 Frag *frag;93 int nfrag;94 Mem *bigmem;95 int nbigmem;96 Mem *smallmem;97 int nsmallmem;98 } freelist;100 #define FRAGSIZE(f) ((f)->wp - (f)->rp)101 #define FRAGASIZE(f) ((f)->mem ? (f)->mem->ep - (f)->mem->bp : 0)103 #define NOTFREE(p) assert((p)->size>=0)/*; checkpacket(p)*/105 Packet *106 packetalloc(void)107 {108 Packet *p;110 lock(&freelist.lk);111 p = freelist.packet;112 if(p != nil)113 freelist.packet = p->next;114 else115 freelist.npacket++;116 unlock(&freelist.lk);118 if(p == nil)119 p = vtbrk(sizeof(Packet));120 else121 assert(p->size == -1);122 p->size = 0;123 p->asize = 0;124 p->first = nil;125 p->last = nil;126 p->next = nil;127 p->pc = getcallerpc((char*)&p+8); /* might not work, but fine */129 NOTFREE(p);130 return p;131 }133 void134 packetfree(Packet *p)135 {136 Frag *f, *ff;138 if(p == nil)139 return;141 NOTFREE(p);142 p->pc = getcallerpc(&p);144 for(f=p->first; f!=nil; f=ff) {145 ff = f->next;146 fragfree(f);147 }148 p->first = (void*)0xDeadBeef;149 p->last = (void*)0xDeadBeef;150 p->size = -1;152 lock(&freelist.lk);153 p->next = freelist.packet;154 freelist.packet = p;155 unlock(&freelist.lk);156 }158 Packet *159 packetdup(Packet *p, int offset, int n)160 {161 Frag *f, *ff;162 Packet *pp;164 NOTFREE(p);165 if(offset < 0 || n < 0 || offset+n > p->size) {166 werrstr(EBadSize);167 return nil;168 }170 pp = packetalloc();171 pp->pc = getcallerpc(&p);172 if(n == 0){173 NOTFREE(pp);174 return pp;175 }177 pp->size = n;179 /* skip offset */180 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)181 offset -= FRAGSIZE(f);183 /* first frag */184 ff = fragdup(pp, f);185 ff->rp += offset;186 pp->first = ff;187 n -= FRAGSIZE(ff);188 pp->asize += FRAGASIZE(ff);190 /* the remaining */191 while(n > 0) {192 f = f->next;193 ff->next = fragdup(pp, f);194 ff = ff->next;195 n -= FRAGSIZE(ff);196 pp->asize += FRAGASIZE(ff);197 }199 /* fix up last frag: note n <= 0 */200 ff->wp += n;201 ff->next = nil;202 pp->last = ff;204 NOTFREE(pp);205 NOTFREE(p);206 return pp;207 }209 Packet *210 packetsplit(Packet *p, int n)211 {212 Packet *pp;213 Frag *f, *ff;215 NOTFREE(p);216 if(n < 0 || n > p->size) {217 werrstr(EPacketSize);218 return nil;219 }221 pp = packetalloc();222 pp->pc = getcallerpc(&p);223 if(n == 0){224 NOTFREE(pp);225 return pp;226 }228 pp->size = n;229 p->size -= n;230 ff = nil;231 for(f=p->first; n > 0 && n >= FRAGSIZE(f); f=f->next) {232 n -= FRAGSIZE(f);233 p->asize -= FRAGASIZE(f);234 pp->asize += FRAGASIZE(f);235 f->p = pp;236 ff = f;237 }239 /* split shared frag */240 if(n > 0) {241 f->p = pp;242 ff = f;243 f = fragdup(p, ff);244 pp->asize += FRAGASIZE(ff);245 ff->wp = ff->rp + n;246 f->rp += n;247 }249 pp->first = p->first;250 pp->last = ff;251 ff->next = nil;252 p->first = f;253 if(f == nil || f->next == nil)254 p->last = f;255 NOTFREE(pp);256 NOTFREE(p);257 return pp;258 }260 int261 packetconsume(Packet *p, uchar *buf, int n)262 {263 NOTFREE(p);264 if(buf && packetcopy(p, buf, 0, n) < 0)265 return -1;266 return packettrim(p, n, p->size-n);267 }269 int270 packettrim(Packet *p, int offset, int n)271 {272 Frag *f, *ff;274 NOTFREE(p);275 if(offset < 0 || offset > p->size) {276 werrstr(EPacketOffset);277 return -1;278 }280 if(n < 0 || offset + n > p->size) {281 werrstr(EPacketOffset);282 return -1;283 }285 p->size = n;287 /* easy case */288 if(n == 0) {289 for(f=p->first; f != nil; f=ff) {290 ff = f->next;291 fragfree(f);292 }293 p->first = p->last = nil;294 p->asize = 0;295 NOTFREE(p);296 return 0;297 }299 /* free before offset */300 for(f=p->first; offset >= FRAGSIZE(f); f=ff) {301 p->asize -= FRAGASIZE(f);302 offset -= FRAGSIZE(f);303 ff = f->next;304 fragfree(f);305 }307 /* adjust frag */308 f->rp += offset;309 p->first = f;311 /* skip middle */312 for(; n > 0 && n > FRAGSIZE(f); f=f->next)313 n -= FRAGSIZE(f);315 /* adjust end */316 f->wp = f->rp + n;317 p->last = f;318 ff = f->next;319 f->next = nil;321 /* free after */322 for(f=ff; f != nil; f=ff) {323 p->asize -= FRAGASIZE(f);324 ff = f->next;325 fragfree(f);326 }327 NOTFREE(p);328 return 0;329 }331 uchar *332 packetheader(Packet *p, int n)333 {334 Frag *f;335 Mem *m;337 NOTFREE(p);338 if(n <= 0 || n > MaxFragSize) {339 werrstr(EPacketSize);340 return nil;341 }343 p->size += n;345 /* try and fix in current frag */346 f = p->first;347 if(f != nil) {348 m = f->mem;349 if(n <= f->rp - m->bp)350 if(m->ref == 1 || memhead(m, f->rp, n) >= 0) {351 f->rp -= n;352 NOTFREE(p);353 return f->rp;354 }355 }357 /* add frag to front */358 f = fragalloc(p, n, PEnd, p->first);359 p->asize += FRAGASIZE(f);360 if(p->first == nil)361 p->last = f;362 p->first = f;363 NOTFREE(p);364 return f->rp;365 }367 uchar *368 packettrailer(Packet *p, int n)369 {370 Mem *m;371 Frag *f;373 NOTFREE(p);374 if(n <= 0 || n > MaxFragSize) {375 werrstr(EPacketSize);376 return nil;377 }379 p->size += n;381 /* try and fix in current frag */382 if(p->first != nil) {383 f = p->last;384 m = f->mem;385 if(n <= m->ep - f->wp)386 if(m->ref == 1 || memtail(m, f->wp, n) >= 0) {387 f->wp += n;388 NOTFREE(p);389 return f->wp - n;390 }391 }393 /* add frag to end */394 f = fragalloc(p, n, (p->first == nil)?PMiddle:PFront, nil);395 p->asize += FRAGASIZE(f);396 if(p->first == nil)397 p->first = f;398 else399 p->last->next = f;400 p->last = f;401 NOTFREE(p);402 return f->rp;403 }405 void406 packetprefix(Packet *p, uchar *buf, int n)407 {408 Frag *f;409 int nn;410 Mem *m;412 NOTFREE(p);413 if(n <= 0)414 return;416 p->size += n;418 /* try and fix in current frag */419 f = p->first;420 if(f != nil) {421 m = f->mem;422 nn = f->rp - m->bp;423 if(nn > n)424 nn = n;425 if(m->ref == 1 || memhead(m, f->rp, nn) >= 0) {426 f->rp -= nn;427 n -= nn;428 memmove(f->rp, buf+n, nn);429 }430 }432 while(n > 0) {433 nn = n;434 if(nn > MaxFragSize)435 nn = MaxFragSize;436 f = fragalloc(p, nn, PEnd, p->first);437 p->asize += FRAGASIZE(f);438 if(p->first == nil)439 p->last = f;440 p->first = f;441 n -= nn;442 memmove(f->rp, buf+n, nn);443 }444 NOTFREE(p);445 }447 void448 packetappend(Packet *p, uchar *buf, int n)449 {450 Frag *f;451 int nn;452 Mem *m;454 NOTFREE(p);455 if(n <= 0)456 return;458 p->size += n;459 /* try and fix in current frag */460 if(p->first != nil) {461 f = p->last;462 m = f->mem;463 nn = m->ep - f->wp;464 if(nn > n)465 nn = n;466 if(m->ref == 1 || memtail(m, f->wp, nn) >= 0) {467 memmove(f->wp, buf, nn);468 f->wp += nn;469 buf += nn;470 n -= nn;471 }472 }474 while(n > 0) {475 nn = n;476 if(nn > MaxFragSize)477 nn = MaxFragSize;478 f = fragalloc(p, nn, (p->first == nil)?PMiddle:PFront, nil);479 p->asize += FRAGASIZE(f);480 if(p->first == nil)481 p->first = f;482 else483 p->last->next = f;484 p->last = f;485 memmove(f->rp, buf, nn);486 buf += nn;487 n -= nn;488 }489 NOTFREE(p);490 }492 void493 packetconcat(Packet *p, Packet *pp)494 {495 Frag *f;497 NOTFREE(p);498 NOTFREE(pp);499 if(pp->size == 0)500 return;501 p->size += pp->size;502 p->asize += pp->asize;503 for(f=pp->first; f; f=f->next)504 f->p = p;506 if(p->first != nil)507 p->last->next = pp->first;508 else509 p->first = pp->first;511 p->last = pp->last;512 pp->size = 0;513 pp->asize = 0;514 pp->first = nil;515 pp->last = nil;516 NOTFREE(p);517 NOTFREE(pp);518 }520 uchar *521 packetpeek(Packet *p, uchar *buf, int offset, int n)522 {523 Frag *f;524 int nn;525 uchar *b;527 NOTFREE(p);528 if(n == 0)529 return buf;531 if(offset < 0 || offset >= p->size) {532 werrstr(EPacketOffset);533 return nil;534 }536 if(n < 0 || offset + n > p->size) {537 werrstr(EPacketSize);538 return nil;539 }541 /* skip up to offset */542 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)543 offset -= FRAGSIZE(f);545 /* easy case */546 if(offset + n <= FRAGSIZE(f)){547 NOTFREE(p);548 return f->rp + offset;549 }551 for(b=buf; n>0; n -= nn) {552 nn = FRAGSIZE(f) - offset;553 if(nn > n)554 nn = n;555 memmove(b, f->rp+offset, nn);556 offset = 0;557 f = f->next;558 b += nn;559 }561 NOTFREE(p);562 return buf;563 }565 int566 packetcopy(Packet *p, uchar *buf, int offset, int n)567 {568 uchar *b;570 NOTFREE(p);571 b = packetpeek(p, buf, offset, n);572 if(b == nil)573 return -1;574 if(b != buf)575 memmove(buf, b, n);576 return 0;577 }579 int580 packetfragments(Packet *p, IOchunk *io, int nio, int offset)581 {582 Frag *f;583 int size;584 IOchunk *eio;586 NOTFREE(p);587 if(p->size == 0 || nio <= 0)588 return 0;590 if(offset < 0 || offset > p->size) {591 werrstr(EPacketOffset);592 return -1;593 }595 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)596 offset -= FRAGSIZE(f);598 size = 0;599 eio = io + nio;600 for(; f != nil && io < eio; f=f->next) {601 io->addr = f->rp + offset;602 io->len = f->wp - (f->rp + offset);603 offset = 0;604 size += io->len;605 io++;606 }607 for(; io < eio; io++){608 io->addr = nil;609 io->len = 0;610 }611 return size;612 }614 void615 packetstats(void)616 {617 Packet *p;618 Frag *f;619 Mem *m;621 int np, nf, nsm, nbm;623 lock(&freelist.lk);624 np = 0;625 for(p=freelist.packet; p; p=p->next)626 np++;627 nf = 0;628 for(f=freelist.frag; f; f=f->next)629 nf++;630 nsm = 0;631 for(m=freelist.smallmem; m; m=m->next)632 nsm++;633 nbm = 0;634 for(m=freelist.bigmem; m; m=m->next)635 nbm++;637 fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",638 np, freelist.npacket,639 nf, freelist.nfrag,640 nsm, freelist.nsmallmem,641 nbm, freelist.nbigmem);643 unlock(&freelist.lk);644 }647 uint648 packetsize(Packet *p)649 {650 NOTFREE(p);651 if(1) {652 Frag *f;653 int size = 0;655 for(f=p->first; f; f=f->next)656 size += FRAGSIZE(f);657 if(size != p->size)658 fprint(2, "packetsize %d %d\n", size, p->size);659 assert(size == p->size);660 }661 return p->size;662 }664 uint665 packetasize(Packet *p)666 {667 NOTFREE(p);668 if(0) {669 Frag *f;670 int asize = 0;672 for(f=p->first; f; f=f->next)673 asize += FRAGASIZE(f);674 if(asize != p->asize)675 fprint(2, "packetasize %d %d\n", asize, p->asize);676 assert(asize == p->asize);677 }678 return p->asize;679 }681 void682 packetsha1(Packet *p, uchar digest[VtScoreSize])683 {684 DigestState ds;685 Frag *f;686 int size;688 NOTFREE(p);689 memset(&ds, 0, sizeof ds);690 size = p->size;691 for(f=p->first; f; f=f->next) {692 sha1(f->rp, FRAGSIZE(f), nil, &ds);693 size -= FRAGSIZE(f);694 }695 assert(size == 0);696 sha1(nil, 0, digest, &ds);697 }699 int700 packetcmp(Packet *pkt0, Packet *pkt1)701 {702 Frag *f0, *f1;703 int n0, n1, x;705 NOTFREE(pkt0);706 NOTFREE(pkt1);707 f0 = pkt0->first;708 f1 = pkt1->first;710 if(f0 == nil)711 return (f1 == nil)?0:-1;712 if(f1 == nil)713 return 1;714 n0 = FRAGSIZE(f0);715 n1 = FRAGSIZE(f1);717 for(;;) {718 if(n0 < n1) {719 x = memcmp(f0->wp - n0, f1->wp - n1, n0);720 if(x != 0)721 return x;722 n1 -= n0;723 f0 = f0->next;724 if(f0 == nil)725 return -1;726 n0 = FRAGSIZE(f0);727 } else if (n0 > n1) {728 x = memcmp(f0->wp - n0, f1->wp - n1, n1);729 if(x != 0)730 return x;731 n0 -= n1;732 f1 = f1->next;733 if(f1 == nil)734 return 1;735 n1 = FRAGSIZE(f1);736 } else { /* n0 == n1 */737 x = memcmp(f0->wp - n0, f1->wp - n1, n0);738 if(x != 0)739 return x;740 f0 = f0->next;741 f1 = f1->next;742 if(f0 == nil)743 return (f1 == nil)?0:-1;744 if(f1 == nil)745 return 1;746 n0 = FRAGSIZE(f0);747 n1 = FRAGSIZE(f1);748 }749 }750 }752 static Frag *753 fragalloc(Packet *p, int n, int pos, Frag *next)754 {755 Frag *f, *ef;756 Mem *m;758 /* look for local frag */759 f = &p->local[0];760 ef = &p->local[NLocalFrag];761 for(;f<ef; f++) {762 if(f->state == FragLocalFree) {763 f->state = FragLocalAlloc;764 goto Found;765 }766 }767 lock(&freelist.lk);768 f = freelist.frag;769 if(f != nil)770 freelist.frag = f->next;771 else772 freelist.nfrag++;773 unlock(&freelist.lk);775 if(f == nil) {776 f = vtbrk(sizeof(Frag));777 f->state = FragGlobal;778 }780 Found:781 f->next = next;782 f->p = p;784 if(n == 0){785 f->mem = 0;786 f->rp = 0;787 f->wp = 0;788 return f;789 }791 if(pos == PEnd && next == nil)792 pos = PMiddle;793 m = memalloc(n, pos);794 f->mem = m;795 f->rp = m->rp;796 f->wp = m->wp;797 return f;798 }800 Packet*801 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)802 {803 Packet *p;804 Frag *f;806 p = packetalloc();807 p->pc = getcallerpc(&buf);808 f = fragalloc(p, 0, 0, nil);809 f->free = free;810 f->a = a;811 f->next = nil;812 f->rp = buf;813 f->wp = buf+n;815 p->first = f;816 p->last = f;817 p->size = n;818 NOTFREE(p);819 return p;820 }822 static Frag *823 fragdup(Packet *p, Frag *f)824 {825 Frag *ff;826 Mem *m;828 m = f->mem;830 /*831 * m->rp && m->wp can be out of date when ref == 1832 * also, potentially reclaims space from previous frags833 */834 if(m && m->ref == 1) {835 m->rp = f->rp;836 m->wp = f->wp;837 }839 ff = fragalloc(p, 0, 0, nil);840 ff->mem = f->mem;841 ff->rp = f->rp;842 ff->wp = f->wp;843 ff->next = f->next;845 /*846 * We can't duplicate these -- there's no dup function.847 */848 assert(f->free==nil && f->a==nil);850 if(m){851 lock(&m->lk);852 m->ref++;853 unlock(&m->lk);854 }857 return ff;858 }861 static void862 fragfree(Frag *f)863 {864 if(f->mem == nil){865 if(f->free)866 (*f->free)(f->a);867 }else{868 memfree(f->mem);869 f->mem = 0;870 }872 if(f->state == FragLocalAlloc) {873 f->state = FragLocalFree;874 return;875 }877 lock(&freelist.lk);878 f->next = freelist.frag;879 freelist.frag = f;880 unlock(&freelist.lk);881 }883 static Mem *884 memalloc(int n, int pos)885 {886 Mem *m;887 int nn;889 if(n < 0 || n > MaxFragSize) {890 werrstr(EPacketSize);891 return 0;892 }893 if(n <= SmallMemSize) {894 lock(&freelist.lk);895 m = freelist.smallmem;896 if(m != nil)897 freelist.smallmem = m->next;898 else899 freelist.nsmallmem++;900 unlock(&freelist.lk);901 nn = SmallMemSize;902 } else {903 lock(&freelist.lk);904 m = freelist.bigmem;905 if(m != nil)906 freelist.bigmem = m->next;907 else908 freelist.nbigmem++;909 unlock(&freelist.lk);910 nn = BigMemSize;911 }913 if(m == nil) {914 m = vtbrk(sizeof(Mem));915 m->bp = vtbrk(nn);916 m->ep = m->bp + nn;917 }918 assert(m->ref == 0);919 m->ref = 1;921 switch(pos) {922 default:923 assert(0);924 case PFront:925 m->rp = m->bp;926 break;927 case PMiddle:928 /* leave a little bit at end */929 m->rp = m->ep - n - 32;930 break;931 case PEnd:932 m->rp = m->ep - n;933 break;934 }935 /* check we did not blow it */936 if(m->rp < m->bp)937 m->rp = m->bp;938 m->wp = m->rp + n;939 assert(m->rp >= m->bp && m->wp <= m->ep);940 return m;941 }943 static void944 memfree(Mem *m)945 {946 lock(&m->lk);947 m->ref--;948 if(m->ref > 0) {949 unlock(&m->lk);950 return;951 }952 unlock(&m->lk);953 assert(m->ref == 0);955 /* memset(m->bp, 0xEF, m->ep-m->bp); */956 switch(m->ep - m->bp) {957 default:958 assert(0);959 case SmallMemSize:960 lock(&freelist.lk);961 m->next = freelist.smallmem;962 freelist.smallmem = m;963 unlock(&freelist.lk);964 break;965 case BigMemSize:966 lock(&freelist.lk);967 m->next = freelist.bigmem;968 freelist.bigmem = m;969 unlock(&freelist.lk);970 break;971 }972 }974 static int975 memhead(Mem *m, uchar *rp, int n)976 {977 fprint(2, "memhead called\n");978 abort();979 lock(&m->lk);980 if(m->rp != rp) {981 unlock(&m->lk);982 return -1;983 }984 m->rp -= n;985 unlock(&m->lk);986 return 0;987 }989 static int990 memtail(Mem *m, uchar *wp, int n)991 {992 fprint(2, "memtail called\n");993 abort();994 lock(&m->lk);995 if(m->wp != wp) {996 unlock(&m->lk);997 return -1;998 }999 m->wp += n;1000 unlock(&m->lk);1001 return 0;1002 }1004 #ifdef NOTDEF1005 static void1006 checkpacket(Packet *p)1007 {1008 int s, as;1009 Frag *f;1010 Frag *ff;1012 s = 0;1013 as = 0;1014 ff=p->first;1015 for(f=p->first; f; ff=f,f=f->next){1016 assert(f->p == p);1017 s += FRAGSIZE(f);1018 as += FRAGASIZE(f);1019 }1020 assert(s == p->size);1021 assert(as == p->asize);1022 if(p->first)1023 assert(ff==p->last);1024 }1025 #endif