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 }761 static Frag *762 fragalloc(Packet *p, int n, int pos, Frag *next)763 {764 Frag *f, *ef;765 Mem *m;767 /* look for local frag */768 f = &p->local[0];769 ef = &p->local[NLocalFrag];770 for(;f<ef; f++) {771 if(f->state == FragLocalFree) {772 f->state = FragLocalAlloc;773 goto Found;774 }775 }776 lock(&freelist.lk);777 f = freelist.frag;778 if(f != nil)779 freelist.frag = f->next;780 else781 freelist.nfrag++;782 unlock(&freelist.lk);784 if(f == nil) {785 f = vtbrk(sizeof(Frag));786 f->state = FragGlobal;787 }789 Found:790 f->next = next;791 f->p = p;793 if(n == 0){794 f->mem = 0;795 f->rp = 0;796 f->wp = 0;797 return f;798 }800 if(pos == PEnd && next == nil)801 pos = PMiddle;802 m = memalloc(n, pos);803 f->mem = m;804 f->rp = m->rp;805 f->wp = m->wp;806 return f;807 }809 Packet*810 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)811 {812 Packet *p;813 Frag *f;815 p = packetalloc();816 p->pc = getcallerpc(&buf);817 f = fragalloc(p, 0, 0, nil);818 f->free = free;819 f->a = a;820 f->next = nil;821 f->rp = buf;822 f->wp = buf+n;824 p->first = f;825 p->last = f;826 p->size = n;827 NOTFREE(p);828 return p;829 }831 static Frag *832 fragdup(Packet *p, Frag *f)833 {834 Frag *ff;835 Mem *m;837 m = f->mem;839 /*840 * m->rp && m->wp can be out of date when ref == 1841 * also, potentially reclaims space from previous frags842 */843 if(m && m->ref == 1) {844 m->rp = f->rp;845 m->wp = f->wp;846 }848 ff = fragalloc(p, 0, 0, nil);849 ff->mem = f->mem;850 ff->rp = f->rp;851 ff->wp = f->wp;852 ff->next = f->next;854 /*855 * We can't duplicate these -- there's no dup function.856 */857 assert(f->free==nil && f->a==nil);859 if(m){860 lock(&m->lk);861 m->ref++;862 unlock(&m->lk);863 }866 return ff;867 }870 static void871 fragfree(Frag *f)872 {873 if(f->mem == nil){874 if(f->free)875 (*f->free)(f->a);876 }else{877 memfree(f->mem);878 f->mem = 0;879 }881 if(f->state == FragLocalAlloc) {882 f->state = FragLocalFree;883 return;884 }886 lock(&freelist.lk);887 f->next = freelist.frag;888 freelist.frag = f;889 unlock(&freelist.lk);890 }892 static Mem *893 memalloc(int n, int pos)894 {895 Mem *m;896 int nn;898 if(n < 0 || n > MaxFragSize) {899 werrstr(EPacketSize);900 return 0;901 }902 if(n <= SmallMemSize) {903 lock(&freelist.lk);904 m = freelist.smallmem;905 if(m != nil)906 freelist.smallmem = m->next;907 else908 freelist.nsmallmem++;909 unlock(&freelist.lk);910 nn = SmallMemSize;911 } else {912 lock(&freelist.lk);913 m = freelist.bigmem;914 if(m != nil)915 freelist.bigmem = m->next;916 else917 freelist.nbigmem++;918 unlock(&freelist.lk);919 nn = BigMemSize;920 }922 if(m == nil) {923 m = vtbrk(sizeof(Mem));924 m->bp = vtbrk(nn);925 m->ep = m->bp + nn;926 }927 assert(m->ref == 0);928 m->ref = 1;930 switch(pos) {931 default:932 assert(0);933 case PFront:934 m->rp = m->bp;935 break;936 case PMiddle:937 /* leave a little bit at end */938 m->rp = m->ep - n - 32;939 break;940 case PEnd:941 m->rp = m->ep - n;942 break;943 }944 /* check we did not blow it */945 if(m->rp < m->bp)946 m->rp = m->bp;947 m->wp = m->rp + n;948 assert(m->rp >= m->bp && m->wp <= m->ep);949 return m;950 }952 static void953 memfree(Mem *m)954 {955 lock(&m->lk);956 m->ref--;957 if(m->ref > 0) {958 unlock(&m->lk);959 return;960 }961 unlock(&m->lk);962 assert(m->ref == 0);964 /* memset(m->bp, 0xEF, m->ep-m->bp); */965 switch(m->ep - m->bp) {966 default:967 assert(0);968 case SmallMemSize:969 lock(&freelist.lk);970 m->next = freelist.smallmem;971 freelist.smallmem = m;972 unlock(&freelist.lk);973 break;974 case BigMemSize:975 lock(&freelist.lk);976 m->next = freelist.bigmem;977 freelist.bigmem = m;978 unlock(&freelist.lk);979 break;980 }981 }983 static int984 memhead(Mem *m, uchar *rp, int n)985 {986 fprint(2, "memhead called\n");987 abort();988 lock(&m->lk);989 if(m->rp != rp) {990 unlock(&m->lk);991 return -1;992 }993 m->rp -= n;994 unlock(&m->lk);995 return 0;996 }998 static int999 memtail(Mem *m, uchar *wp, int n)1000 {1001 fprint(2, "memtail called\n");1002 abort();1003 lock(&m->lk);1004 if(m->wp != wp) {1005 unlock(&m->lk);1006 return -1;1007 }1008 m->wp += n;1009 unlock(&m->lk);1010 return 0;1011 }1013 #if 01014 static void1015 checkpacket(Packet *p)1016 {1017 int s, as;1018 Frag *f;1019 Frag *ff;1021 s = 0;1022 as = 0;1023 ff=p->first;1024 for(f=p->first; f; ff=f,f=f->next){1025 assert(f->p == p);1026 s += FRAGSIZE(f);1027 as += FRAGASIZE(f);1028 }1029 assert(s == p->size);1030 assert(as == p->asize);1031 if(p->first)1032 assert(ff==p->last);1033 }1034 #endif