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 #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 }616 return size;617 }619 void620 packetstats(void)621 {622 Packet *p;623 Frag *f;624 Mem *m;626 int np, nf, nsm, nbm;628 lock(&freelist.lk);629 np = 0;630 for(p=freelist.packet; p; p=p->next)631 np++;632 nf = 0;633 for(f=freelist.frag; f; f=f->next)634 nf++;635 nsm = 0;636 for(m=freelist.smallmem; m; m=m->next)637 nsm++;638 nbm = 0;639 for(m=freelist.bigmem; m; m=m->next)640 nbm++;642 fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",643 np, freelist.npacket,644 nf, freelist.nfrag,645 nsm, freelist.nsmallmem,646 nbm, freelist.nbigmem);648 unlock(&freelist.lk);649 }652 uint653 packetsize(Packet *p)654 {655 NOTFREE(p);656 if(1) {657 Frag *f;658 int size = 0;660 for(f=p->first; f; f=f->next)661 size += FRAGSIZE(f);662 if(size != p->size)663 fprint(2, "packetsize %d %d\n", size, p->size);664 assert(size == p->size);665 }666 return p->size;667 }669 uint670 packetasize(Packet *p)671 {672 NOTFREE(p);673 if(0) {674 Frag *f;675 int asize = 0;677 for(f=p->first; f; f=f->next)678 asize += FRAGASIZE(f);679 if(asize != p->asize)680 fprint(2, "packetasize %d %d\n", asize, p->asize);681 assert(asize == p->asize);682 }683 return p->asize;684 }686 void687 packetsha1(Packet *p, uchar digest[VtScoreSize])688 {689 DigestState ds;690 Frag *f;691 int size;693 NOTFREE(p);694 memset(&ds, 0, sizeof ds);695 size = p->size;696 for(f=p->first; f; f=f->next) {697 sha1(f->rp, FRAGSIZE(f), nil, &ds);698 size -= FRAGSIZE(f);699 }700 assert(size == 0);701 sha1(nil, 0, digest, &ds);702 }704 int705 packetcmp(Packet *pkt0, Packet *pkt1)706 {707 Frag *f0, *f1;708 int n0, n1, x;710 NOTFREE(pkt0);711 NOTFREE(pkt1);712 f0 = pkt0->first;713 f1 = pkt1->first;715 if(f0 == nil)716 return (f1 == nil)?0:-1;717 if(f1 == nil)718 return 1;719 n0 = FRAGSIZE(f0);720 n1 = FRAGSIZE(f1);722 for(;;) {723 if(n0 < n1) {724 x = memcmp(f0->wp - n0, f1->wp - n1, n0);725 if(x != 0)726 return x;727 n1 -= n0;728 f0 = f0->next;729 if(f0 == nil)730 return -1;731 n0 = FRAGSIZE(f0);732 } else if (n0 > n1) {733 x = memcmp(f0->wp - n0, f1->wp - n1, n1);734 if(x != 0)735 return x;736 n0 -= n1;737 f1 = f1->next;738 if(f1 == nil)739 return 1;740 n1 = FRAGSIZE(f1);741 } else { /* n0 == n1 */742 x = memcmp(f0->wp - n0, f1->wp - n1, n0);743 if(x != 0)744 return x;745 f0 = f0->next;746 f1 = f1->next;747 if(f0 == nil)748 return (f1 == nil)?0:-1;749 if(f1 == nil)750 return 1;751 n0 = FRAGSIZE(f0);752 n1 = FRAGSIZE(f1);753 }754 }755 }758 static Frag *759 fragalloc(Packet *p, int n, int pos, Frag *next)760 {761 Frag *f, *ef;762 Mem *m;764 /* look for local frag */765 f = &p->local[0];766 ef = &p->local[NLocalFrag];767 for(;f<ef; f++) {768 if(f->state == FragLocalFree) {769 f->state = FragLocalAlloc;770 goto Found;771 }772 }773 lock(&freelist.lk);774 f = freelist.frag;775 if(f != nil)776 freelist.frag = f->next;777 else778 freelist.nfrag++;779 unlock(&freelist.lk);781 if(f == nil) {782 f = vtbrk(sizeof(Frag));783 f->state = FragGlobal;784 }786 Found:787 f->next = next;788 f->p = p;790 if(n == 0){791 f->mem = 0;792 f->rp = 0;793 f->wp = 0;794 return f;795 }797 if(pos == PEnd && next == nil)798 pos = PMiddle;799 m = memalloc(n, pos);800 f->mem = m;801 f->rp = m->rp;802 f->wp = m->wp;803 return f;804 }806 Packet*807 packetforeign(uchar *buf, int n, void (*free)(void *a), void *a)808 {809 Packet *p;810 Frag *f;812 p = packetalloc();813 p->pc = getcallerpc(&buf);814 f = fragalloc(p, 0, 0, nil);815 f->free = free;816 f->a = a;817 f->next = nil;818 f->rp = buf;819 f->wp = buf+n;821 p->first = f;822 p->last = f;823 p->size = n;824 NOTFREE(p);825 return p;826 }828 static Frag *829 fragdup(Packet *p, Frag *f)830 {831 Frag *ff;832 Mem *m;834 m = f->mem;836 /*837 * m->rp && m->wp can be out of date when ref == 1838 * also, potentially reclaims space from previous frags839 */840 if(m && m->ref == 1) {841 m->rp = f->rp;842 m->wp = f->wp;843 }845 ff = fragalloc(p, 0, 0, nil);846 ff->mem = f->mem;847 ff->rp = f->rp;848 ff->wp = f->wp;849 ff->next = f->next;851 /*852 * We can't duplicate these -- there's no dup function.853 */854 assert(f->free==nil && f->a==nil);856 if(m){857 lock(&m->lk);858 m->ref++;859 unlock(&m->lk);860 }863 return ff;864 }867 static void868 fragfree(Frag *f)869 {870 if(f->mem == nil){871 if(f->free)872 (*f->free)(f->a);873 }else{874 memfree(f->mem);875 f->mem = 0;876 }878 if(f->state == FragLocalAlloc) {879 f->state = FragLocalFree;880 return;881 }883 lock(&freelist.lk);884 f->next = freelist.frag;885 freelist.frag = f;886 unlock(&freelist.lk);887 }889 static Mem *890 memalloc(int n, int pos)891 {892 Mem *m;893 int nn;895 if(n < 0 || n > MaxFragSize) {896 werrstr(EPacketSize);897 return 0;898 }899 if(n <= SmallMemSize) {900 lock(&freelist.lk);901 m = freelist.smallmem;902 if(m != nil)903 freelist.smallmem = m->next;904 else905 freelist.nsmallmem++;906 unlock(&freelist.lk);907 nn = SmallMemSize;908 } else {909 lock(&freelist.lk);910 m = freelist.bigmem;911 if(m != nil)912 freelist.bigmem = m->next;913 else914 freelist.nbigmem++;915 unlock(&freelist.lk);916 nn = BigMemSize;917 }919 if(m == nil) {920 m = vtbrk(sizeof(Mem));921 m->bp = vtbrk(nn);922 m->ep = m->bp + nn;923 }924 assert(m->ref == 0);925 m->ref = 1;927 switch(pos) {928 default:929 assert(0);930 case PFront:931 m->rp = m->bp;932 break;933 case PMiddle:934 /* leave a little bit at end */935 m->rp = m->ep - n - 32;936 break;937 case PEnd:938 m->rp = m->ep - n;939 break;940 }941 /* check we did not blow it */942 if(m->rp < m->bp)943 m->rp = m->bp;944 m->wp = m->rp + n;945 assert(m->rp >= m->bp && m->wp <= m->ep);946 return m;947 }949 static void950 memfree(Mem *m)951 {952 lock(&m->lk);953 m->ref--;954 if(m->ref > 0) {955 unlock(&m->lk);956 return;957 }958 unlock(&m->lk);959 assert(m->ref == 0);961 /* memset(m->bp, 0xEF, m->ep-m->bp); */962 switch(m->ep - m->bp) {963 default:964 assert(0);965 case SmallMemSize:966 lock(&freelist.lk);967 m->next = freelist.smallmem;968 freelist.smallmem = m;969 unlock(&freelist.lk);970 break;971 case BigMemSize:972 lock(&freelist.lk);973 m->next = freelist.bigmem;974 freelist.bigmem = m;975 unlock(&freelist.lk);976 break;977 }978 }980 static int981 memhead(Mem *m, uchar *rp, int n)982 {983 fprint(2, "memhead called\n");984 abort();985 lock(&m->lk);986 if(m->rp != rp) {987 unlock(&m->lk);988 return -1;989 }990 m->rp -= n;991 unlock(&m->lk);992 return 0;993 }995 static int996 memtail(Mem *m, uchar *wp, int n)997 {998 fprint(2, "memtail called\n");999 abort();1000 lock(&m->lk);1001 if(m->wp != wp) {1002 unlock(&m->lk);1003 return -1;1004 }1005 m->wp += n;1006 unlock(&m->lk);1007 return 0;1008 }1010 #if 01011 static void1012 checkpacket(Packet *p)1013 {1014 int s, as;1015 Frag *f;1016 Frag *ff;1018 s = 0;1019 as = 0;1020 ff=p->first;1021 for(f=p->first; f; ff=f,f=f->next){1022 assert(f->p == p);1023 s += FRAGSIZE(f);1024 as += FRAGASIZE(f);1025 }1026 assert(s == p->size);1027 assert(as == p->asize);1028 if(p->first)1029 assert(ff==p->last);1030 }1031 #endif