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 #if 079 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 /*if(0)fprint(2, "packetalloc %p from %08lux %08lux %08lux\n", p, *((uint*)&p+2), *((uint*)&p+3), *((uint*)&p+4)); */131 NOTFREE(p);132 return p;133 }135 void136 packetfree(Packet *p)137 {138 Frag *f, *ff;140 /*if(1)fprint(2, "packetfree %p from %08lux\n", p, getcallerpc(&p)); */142 if(p == nil)143 return;145 NOTFREE(p);146 p->pc = getcallerpc(&p);148 for(f=p->first; f!=nil; f=ff) {149 ff = f->next;150 fragfree(f);151 }152 p->first = (void*)0xDeadBeef;153 p->last = (void*)0xDeadBeef;154 p->size = -1;156 lock(&freelist.lk);157 p->next = freelist.packet;158 freelist.packet = p;159 unlock(&freelist.lk);160 }162 Packet *163 packetdup(Packet *p, int offset, int n)164 {165 Frag *f, *ff;166 Packet *pp;168 NOTFREE(p);169 if(offset < 0 || n < 0 || offset+n > p->size) {170 werrstr(EBadSize);171 return nil;172 }174 pp = packetalloc();175 pp->pc = getcallerpc(&p);176 if(n == 0){177 NOTFREE(pp);178 return pp;179 }181 pp->size = n;183 /* skip offset */184 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)185 offset -= FRAGSIZE(f);187 /* first frag */188 ff = fragdup(pp, f);189 ff->rp += offset;190 pp->first = ff;191 n -= FRAGSIZE(ff);192 pp->asize += FRAGASIZE(ff);194 /* the remaining */195 while(n > 0) {196 f = f->next;197 ff->next = fragdup(pp, f);198 ff = ff->next;199 n -= FRAGSIZE(ff);200 pp->asize += FRAGASIZE(ff);201 }203 /* fix up last frag: note n <= 0 */204 ff->wp += n;205 ff->next = nil;206 pp->last = ff;208 NOTFREE(pp);209 NOTFREE(p);210 return pp;211 }213 Packet *214 packetsplit(Packet *p, int n)215 {216 Packet *pp;217 Frag *f, *ff;219 if(0) fprint(2, "packetsplit %p %d\n", p, n);220 NOTFREE(p);221 if(n < 0 || n > p->size) {222 werrstr(EPacketSize);223 return nil;224 }226 pp = packetalloc();227 pp->pc = getcallerpc(&p);228 if(n == 0){229 NOTFREE(pp);230 return pp;231 }233 pp->size = n;234 p->size -= n;235 ff = nil;236 for(f=p->first; n > 0 && n >= FRAGSIZE(f); f=f->next) {237 n -= FRAGSIZE(f);238 p->asize -= FRAGASIZE(f);239 pp->asize += FRAGASIZE(f);240 f->p = pp;241 ff = f;242 }244 /* split shared frag */245 if(n > 0) {246 f->p = pp;247 ff = f;248 f = fragdup(p, ff);249 pp->asize += FRAGASIZE(ff);250 ff->wp = ff->rp + n;251 f->rp += n;252 }254 pp->first = p->first;255 pp->last = ff;256 ff->next = nil;257 p->first = f;258 if(f == nil || f->next == nil)259 p->last = f;260 NOTFREE(pp);261 NOTFREE(p);262 return pp;263 }265 int266 packetconsume(Packet *p, uchar *buf, int n)267 {268 if(0) fprint(2, "packetconsume %p %d\n", p, n);269 NOTFREE(p);270 if(buf && packetcopy(p, buf, 0, n) < 0)271 return -1;272 return packettrim(p, n, p->size-n);273 }275 int276 packettrim(Packet *p, int offset, int n)277 {278 Frag *f, *ff;280 if(0) fprint(2, "packettrim %p %d %d\n", p, offset, n);281 NOTFREE(p);282 if(offset < 0 || offset > p->size) {283 werrstr(EPacketOffset);284 return -1;285 }287 if(n < 0 || offset + n > p->size) {288 werrstr(EPacketOffset);289 return -1;290 }292 p->size = n;294 /* easy case */295 if(n == 0) {296 for(f=p->first; f != nil; f=ff) {297 ff = f->next;298 fragfree(f);299 }300 p->first = p->last = nil;301 p->asize = 0;302 NOTFREE(p);303 return 0;304 }306 /* free before offset */307 for(f=p->first; offset >= FRAGSIZE(f); f=ff) {308 p->asize -= FRAGASIZE(f);309 offset -= FRAGSIZE(f);310 ff = f->next;311 fragfree(f);312 }314 /* adjust frag */315 f->rp += offset;316 p->first = f;318 /* skip middle */319 for(; n > 0 && n > FRAGSIZE(f); f=f->next)320 n -= FRAGSIZE(f);322 /* adjust end */323 f->wp = f->rp + n;324 p->last = f;325 ff = f->next;326 f->next = nil;328 /* free after */329 for(f=ff; f != nil; f=ff) {330 p->asize -= FRAGASIZE(f);331 ff = f->next;332 fragfree(f);333 }334 NOTFREE(p);335 return 0;336 }338 uchar *339 packetheader(Packet *p, int n)340 {341 Frag *f;342 Mem *m;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 f = p->first;354 if(f != nil) {355 m = f->mem;356 if(n <= f->rp - m->bp)357 if(m->ref == 1 || memhead(m, f->rp, n) >= 0) {358 f->rp -= n;359 NOTFREE(p);360 return f->rp;361 }362 }364 /* add frag to front */365 f = fragalloc(p, n, PEnd, p->first);366 p->asize += FRAGASIZE(f);367 if(p->first == nil)368 p->last = f;369 p->first = f;370 NOTFREE(p);371 return f->rp;372 }374 uchar *375 packettrailer(Packet *p, int n)376 {377 Mem *m;378 Frag *f;380 if(0) fprint(2, "packettrailer %p %d\n", p, n);381 NOTFREE(p);382 if(n <= 0 || n > MaxFragSize) {383 werrstr(EPacketSize);384 return nil;385 }387 p->size += n;389 /* try and fix in current frag */390 if(p->first != nil) {391 f = p->last;392 m = f->mem;393 if(n <= m->ep - f->wp)394 if(m->ref == 1 || memtail(m, f->wp, n) >= 0) {395 f->wp += n;396 NOTFREE(p);397 return f->wp - n;398 }399 }401 /* add frag to end */402 f = fragalloc(p, n, (p->first == nil)?PMiddle:PFront, nil);403 p->asize += FRAGASIZE(f);404 if(p->first == nil)405 p->first = f;406 else407 p->last->next = f;408 p->last = f;409 NOTFREE(p);410 return f->rp;411 }413 void414 packetprefix(Packet *p, uchar *buf, int n)415 {416 Frag *f;417 int nn;418 Mem *m;420 NOTFREE(p);421 if(n <= 0)422 return;424 p->size += n;426 /* try and fix in current frag */427 f = p->first;428 if(f != nil) {429 m = f->mem;430 nn = f->rp - m->bp;431 if(nn > n)432 nn = n;433 if(m->ref == 1 || memhead(m, f->rp, nn) >= 0) {434 f->rp -= nn;435 n -= nn;436 memmove(f->rp, buf+n, nn);437 }438 }440 while(n > 0) {441 nn = n;442 if(nn > MaxFragSize)443 nn = MaxFragSize;444 f = fragalloc(p, nn, PEnd, p->first);445 p->asize += FRAGASIZE(f);446 if(p->first == nil)447 p->last = f;448 p->first = f;449 n -= nn;450 memmove(f->rp, buf+n, nn);451 }452 NOTFREE(p);453 }455 void456 packetappend(Packet *p, uchar *buf, int n)457 {458 Frag *f;459 int nn;460 Mem *m;462 NOTFREE(p);463 if(n <= 0)464 return;466 p->size += n;467 /* try and fix in current frag */468 if(p->first != nil) {469 f = p->last;470 m = f->mem;471 nn = m->ep - f->wp;472 if(nn > n)473 nn = n;474 if(m->ref == 1 || memtail(m, f->wp, nn) >= 0) {475 memmove(f->wp, buf, nn);476 f->wp += nn;477 buf += nn;478 n -= nn;479 }480 }482 while(n > 0) {483 nn = n;484 if(nn > MaxFragSize)485 nn = MaxFragSize;486 f = fragalloc(p, nn, (p->first == nil)?PMiddle:PFront, nil);487 p->asize += FRAGASIZE(f);488 if(p->first == nil)489 p->first = f;490 else491 p->last->next = f;492 p->last = f;493 memmove(f->rp, buf, nn);494 buf += nn;495 n -= nn;496 }497 NOTFREE(p);498 }500 void501 packetconcat(Packet *p, Packet *pp)502 {503 Frag *f;505 NOTFREE(p);506 NOTFREE(pp);507 if(pp->size == 0)508 return;509 p->size += pp->size;510 p->asize += pp->asize;511 for(f=pp->first; f; f=f->next)512 f->p = p;514 if(p->first != nil)515 p->last->next = pp->first;516 else517 p->first = pp->first;519 p->last = pp->last;520 pp->size = 0;521 pp->asize = 0;522 pp->first = nil;523 pp->last = nil;524 NOTFREE(p);525 NOTFREE(pp);526 }528 uchar *529 packetpeek(Packet *p, uchar *buf, int offset, int n)530 {531 Frag *f;532 int nn;533 uchar *b;535 NOTFREE(p);536 if(n == 0)537 return buf;539 if(offset < 0 || offset >= p->size) {540 werrstr(EPacketOffset);541 return nil;542 }544 if(n < 0 || offset + n > p->size) {545 werrstr(EPacketSize);546 return nil;547 }549 /* skip up to offset */550 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)551 offset -= FRAGSIZE(f);553 /* easy case */554 if(offset + n <= FRAGSIZE(f)){555 NOTFREE(p);556 return f->rp + offset;557 }559 for(b=buf; n>0; n -= nn) {560 nn = FRAGSIZE(f) - offset;561 if(nn > n)562 nn = n;563 memmove(b, f->rp+offset, nn);564 offset = 0;565 f = f->next;566 b += nn;567 }569 NOTFREE(p);570 return buf;571 }573 int574 packetcopy(Packet *p, uchar *buf, int offset, int n)575 {576 uchar *b;578 NOTFREE(p);579 b = packetpeek(p, buf, offset, n);580 if(b == nil)581 return -1;582 if(b != buf)583 memmove(buf, b, n);584 return 0;585 }587 int588 packetfragments(Packet *p, IOchunk *io, int nio, int offset)589 {590 Frag *f;591 int size;592 IOchunk *eio;594 NOTFREE(p);595 if(p->size == 0 || nio <= 0)596 return 0;598 if(offset < 0 || offset > p->size) {599 werrstr(EPacketOffset);600 return -1;601 }603 for(f=p->first; offset >= FRAGSIZE(f); f=f->next)604 offset -= FRAGSIZE(f);606 size = 0;607 eio = io + nio;608 for(; f != nil && io < eio; f=f->next) {609 io->addr = f->rp + offset;610 io->len = f->wp - (f->rp + offset);611 offset = 0;612 size += io->len;613 io++;614 }615 for(; io < eio; io++){616 io->addr = nil;617 io->len = 0;618 }619 return size;620 }622 void623 packetstats(void)624 {625 Packet *p;626 Frag *f;627 Mem *m;629 int np, nf, nsm, nbm;631 lock(&freelist.lk);632 np = 0;633 for(p=freelist.packet; p; p=p->next)634 np++;635 nf = 0;636 for(f=freelist.frag; f; f=f->next)637 nf++;638 nsm = 0;639 for(m=freelist.smallmem; m; m=m->next)640 nsm++;641 nbm = 0;642 for(m=freelist.bigmem; m; m=m->next)643 nbm++;645 fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",646 np, freelist.npacket,647 nf, freelist.nfrag,648 nsm, freelist.nsmallmem,649 nbm, freelist.nbigmem);651 unlock(&freelist.lk);652 }655 uint656 packetsize(Packet *p)657 {658 NOTFREE(p);659 if(1) {660 Frag *f;661 int size = 0;663 for(f=p->first; f; f=f->next)664 size += FRAGSIZE(f);665 if(size != p->size)666 fprint(2, "packetsize %d %d\n", size, p->size);667 assert(size == p->size);668 }669 return p->size;670 }672 uint673 packetasize(Packet *p)674 {675 NOTFREE(p);676 if(0) {677 Frag *f;678 int asize = 0;680 for(f=p->first; f; f=f->next)681 asize += FRAGASIZE(f);682 if(asize != p->asize)683 fprint(2, "packetasize %d %d\n", asize, p->asize);684 assert(asize == p->asize);685 }686 return p->asize;687 }689 void690 packetsha1(Packet *p, uchar digest[VtScoreSize])691 {692 DigestState ds;693 Frag *f;694 int size;696 NOTFREE(p);697 memset(&ds, 0, sizeof ds);698 size = p->size;699 for(f=p->first; f; f=f->next) {700 sha1(f->rp, FRAGSIZE(f), nil, &ds);701 size -= FRAGSIZE(f);702 }703 assert(size == 0);704 sha1(nil, 0, digest, &ds);705 }707 int708 packetcmp(Packet *pkt0, Packet *pkt1)709 {710 Frag *f0, *f1;711 int n0, n1, x;713 NOTFREE(pkt0);714 NOTFREE(pkt1);715 f0 = pkt0->first;716 f1 = pkt1->first;718 if(f0 == nil)719 return (f1 == nil)?0:-1;720 if(f1 == nil)721 return 1;722 n0 = FRAGSIZE(f0);723 n1 = FRAGSIZE(f1);725 for(;;) {726 if(n0 < n1) {727 x = memcmp(f0->wp - n0, f1->wp - n1, n0);728 if(x != 0)729 return x;730 n1 -= n0;731 f0 = f0->next;732 if(f0 == nil)733 return -1;734 n0 = FRAGSIZE(f0);735 } else if (n0 > n1) {736 x = memcmp(f0->wp - n0, f1->wp - n1, n1);737 if(x != 0)738 return x;739 n0 -= n1;740 f1 = f1->next;741 if(f1 == nil)742 return 1;743 n1 = FRAGSIZE(f1);744 } else { /* n0 == n1 */745 x = memcmp(f0->wp - n0, f1->wp - n1, n0);746 if(x != 0)747 return x;748 f0 = f0->next;749 f1 = f1->next;750 if(f0 == nil)751 return (f1 == nil)?0:-1;752 if(f1 == nil)753 return 1;754 n0 = FRAGSIZE(f0);755 n1 = FRAGSIZE(f1);756 }757 }758 }760 static Frag *761 fragalloc(Packet *p, int n, int pos, Frag *next)762 {763 Frag *f, *ef;764 Mem *m;766 /* look for local frag */767 f = &p->local[0];768 ef = &p->local[NLocalFrag];769 for(;f<ef; f++) {770 if(f->state == FragLocalFree) {771 f->state = FragLocalAlloc;772 goto Found;773 }774 }775 lock(&freelist.lk);776 f = freelist.frag;777 if(f != nil)778 freelist.frag = f->next;779 else780 freelist.nfrag++;781 unlock(&freelist.lk);783 if(f == nil) {784 f = vtbrk(sizeof(Frag));785 f->state = FragGlobal;786 }788 Found:789 f->next = next;790 f->p = p;792 if(n == 0){793 f->mem = 0;794 f->rp = 0;795 f->wp = 0;796 return f;797 }799 if(pos == PEnd && next == nil)800 pos = PMiddle;801 m = memalloc(n, pos);802 f->mem = m;803 f->rp = m->rp;804 f->wp = m->wp;805 return f;806 }808 Packet*809 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)810 {811 Packet *p;812 Frag *f;814 p = packetalloc();815 p->pc = getcallerpc(&buf);816 f = fragalloc(p, 0, 0, nil);817 f->free = free;818 f->a = a;819 f->next = nil;820 f->rp = buf;821 f->wp = buf+n;823 p->first = f;824 p->last = f;825 p->size = n;826 NOTFREE(p);827 return p;828 }830 static Frag *831 fragdup(Packet *p, Frag *f)832 {833 Frag *ff;834 Mem *m;836 m = f->mem;838 /*839 * m->rp && m->wp can be out of date when ref == 1840 * also, potentially reclaims space from previous frags841 */842 if(m && m->ref == 1) {843 m->rp = f->rp;844 m->wp = f->wp;845 }847 ff = fragalloc(p, 0, 0, nil);848 ff->mem = f->mem;849 ff->rp = f->rp;850 ff->wp = f->wp;851 ff->next = f->next;853 /*854 * We can't duplicate these -- there's no dup function.855 */856 assert(f->free==nil && f->a==nil);858 if(m){859 lock(&m->lk);860 m->ref++;861 unlock(&m->lk);862 }865 return ff;866 }869 static void870 fragfree(Frag *f)871 {872 if(f->mem == nil){873 if(f->free)874 (*f->free)(f->a);875 }else{876 memfree(f->mem);877 f->mem = 0;878 }880 if(f->state == FragLocalAlloc) {881 f->state = FragLocalFree;882 return;883 }885 lock(&freelist.lk);886 f->next = freelist.frag;887 freelist.frag = f;888 unlock(&freelist.lk);889 }891 static Mem *892 memalloc(int n, int pos)893 {894 Mem *m;895 int nn;897 if(n < 0 || n > MaxFragSize) {898 werrstr(EPacketSize);899 return 0;900 }901 if(n <= SmallMemSize) {902 lock(&freelist.lk);903 m = freelist.smallmem;904 if(m != nil)905 freelist.smallmem = m->next;906 else907 freelist.nsmallmem++;908 unlock(&freelist.lk);909 nn = SmallMemSize;910 } else {911 lock(&freelist.lk);912 m = freelist.bigmem;913 if(m != nil)914 freelist.bigmem = m->next;915 else916 freelist.nbigmem++;917 unlock(&freelist.lk);918 nn = BigMemSize;919 }921 if(m == nil) {922 m = vtbrk(sizeof(Mem));923 m->bp = vtbrk(nn);924 m->ep = m->bp + nn;925 }926 assert(m->ref == 0);927 m->ref = 1;929 switch(pos) {930 default:931 assert(0);932 case PFront:933 m->rp = m->bp;934 break;935 case PMiddle:936 /* leave a little bit at end */937 m->rp = m->ep - n - 32;938 break;939 case PEnd:940 m->rp = m->ep - n;941 break;942 }943 /* check we did not blow it */944 if(m->rp < m->bp)945 m->rp = m->bp;946 m->wp = m->rp + n;947 assert(m->rp >= m->bp && m->wp <= m->ep);948 return m;949 }951 static void952 memfree(Mem *m)953 {954 lock(&m->lk);955 m->ref--;956 if(m->ref > 0) {957 unlock(&m->lk);958 return;959 }960 unlock(&m->lk);961 assert(m->ref == 0);963 /* memset(m->bp, 0xEF, m->ep-m->bp); */964 switch(m->ep - m->bp) {965 default:966 assert(0);967 case SmallMemSize:968 lock(&freelist.lk);969 m->next = freelist.smallmem;970 freelist.smallmem = m;971 unlock(&freelist.lk);972 break;973 case BigMemSize:974 lock(&freelist.lk);975 m->next = freelist.bigmem;976 freelist.bigmem = m;977 unlock(&freelist.lk);978 break;979 }980 }982 static int983 memhead(Mem *m, uchar *rp, int n)984 {985 fprint(2, "memhead called\n");986 abort();987 lock(&m->lk);988 if(m->rp != rp) {989 unlock(&m->lk);990 return -1;991 }992 m->rp -= n;993 unlock(&m->lk);994 return 0;995 }997 static int998 memtail(Mem *m, uchar *wp, int n)999 {1000 fprint(2, "memtail called\n");1001 abort();1002 lock(&m->lk);1003 if(m->wp != wp) {1004 unlock(&m->lk);1005 return -1;1006 }1007 m->wp += n;1008 unlock(&m->lk);1009 return 0;1010 }1012 #if 01013 static void1014 checkpacket(Packet *p)1015 {1016 int s, as;1017 Frag *f;1018 Frag *ff;1020 s = 0;1021 as = 0;1022 ff=p->first;1023 for(f=p->first; f; ff=f,f=f->next){1024 assert(f->p == p);1025 s += FRAGSIZE(f);1026 as += FRAGASIZE(f);1027 }1028 assert(s == p->size);1029 assert(as == p->asize);1030 if(p->first)1031 assert(ff==p->last);1032 }1033 #endif