123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857 |
- /*
- * This file is part of the UCB release of Plan 9. It is subject to the license
- * terms in the LICENSE file found in the top-level directory of this
- * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
- * part of the UCB release of Plan 9, including this file, may be copied,
- * modified, propagated, or distributed except according to the terms contained
- * in the LICENSE file.
- */
- #include <u.h>
- #include <libc.h>
- #include <oventi.h>
- #include "packet.h"
- static Frag *fragAlloc(Packet*, int n, int pos, Frag *next);
- static Frag *fragDup(Packet*, Frag*);
- static void fragFree(Frag*);
- static Mem *memAlloc(int, int);
- static void memFree(Mem*);
- static int memHead(Mem *m, uint8_t *rp, int n);
- static int memTail(Mem *m, uint8_t *wp, int n);
- static char EPacketSize[] = "bad packet size";
- static char EPacketOffset[] = "bad packet offset";
- static char EBadSize[] = "bad size";
- static struct {
- Lock lk;
- Packet *packet;
- int npacket;
- Frag *frag;
- int nfrag;
- Mem *bigMem;
- int nbigMem;
- Mem *smallMem;
- int nsmallMem;
- } freeList;
- #define FRAGSIZE(f) ((f)->wp - (f)->rp)
- #define FRAGASIZE(f) ((f)->mem->ep - (f)->mem->bp)
- #define NOTFREE(p) assert((p)->size>=0)
- Packet *
- packetAlloc(void)
- {
- Packet *p;
- lock(&freeList.lk);
- p = freeList.packet;
- if(p != nil)
- freeList.packet = p->next;
- else
- freeList.npacket++;
- unlock(&freeList.lk);
- if(p == nil)
- p = vtMemBrk(sizeof(Packet));
- else
- assert(p->size == -1);
- p->size = 0;
- p->asize = 0;
- p->first = nil;
- p->last = nil;
- p->next = nil;
- return p;
- }
- void
- packetFree(Packet *p)
- {
- Frag *f, *ff;
- if(0)fprint(2, "packetFree %p\n", p);
- NOTFREE(p);
- p->size = -1;
- for(f=p->first; f!=nil; f=ff) {
- ff = f->next;
- fragFree(f);
- }
- p->first = nil;
- p->last = nil;
- lock(&freeList.lk);
- p->next = freeList.packet;
- freeList.packet = p;
- unlock(&freeList.lk);
- }
- Packet *
- packetDup(Packet *p, int offset, int n)
- {
- Frag *f, *ff;
- Packet *pp;
- NOTFREE(p);
- if(offset < 0 || n < 0 || offset+n > p->size) {
- vtSetError(EBadSize);
- return nil;
- }
- pp = packetAlloc();
- if(n == 0)
- return pp;
- pp->size = n;
- /* skip offset */
- for(f=p->first; offset >= FRAGSIZE(f); f=f->next)
- offset -= FRAGSIZE(f);
- /* first frag */
- ff = fragDup(pp, f);
- ff->rp += offset;
- pp->first = ff;
- n -= FRAGSIZE(ff);
- pp->asize += FRAGASIZE(ff);
- /* the remaining */
- while(n > 0) {
- f = f->next;
- ff->next = fragDup(pp, f);
- ff = ff->next;
- n -= FRAGSIZE(ff);
- pp->asize += FRAGASIZE(ff);
- }
- /* fix up last frag: note n <= 0 */
- ff->wp += n;
- ff->next = nil;
- pp->last = ff;
- return pp;
- }
- Packet *
- packetSplit(Packet *p, int n)
- {
- Packet *pp;
- Frag *f, *ff;
- NOTFREE(p);
- if(n < 0 || n > p->size) {
- vtSetError(EPacketSize);
- return nil;
- }
- pp = packetAlloc();
- if(n == 0)
- return pp;
- pp->size = n;
- p->size -= n;
- ff = nil;
- for(f=p->first; n > 0 && n >= FRAGSIZE(f); f=f->next) {
- n -= FRAGSIZE(f);
- p->asize -= FRAGASIZE(f);
- pp->asize += FRAGASIZE(f);
- ff = f;
- }
- /* split shared frag */
- if(n > 0) {
- ff = f;
- f = fragDup(pp, ff);
- pp->asize += FRAGASIZE(ff);
- ff->next = nil;
- ff->wp = ff->rp + n;
- f->rp += n;
- }
- pp->first = p->first;
- pp->last = ff;
- p->first = f;
- return pp;
- }
- int
- packetConsume(Packet *p, uint8_t *buf, int n)
- {
- NOTFREE(p);
- if(buf && !packetCopy(p, buf, 0, n))
- return 0;
- return packetTrim(p, n, p->size-n);
- }
- int
- packetTrim(Packet *p, int offset, int n)
- {
- Frag *f, *ff;
- NOTFREE(p);
- if(offset < 0 || offset > p->size) {
- vtSetError(EPacketOffset);
- return 0;
- }
- if(n < 0 || offset + n > p->size) {
- vtSetError(EPacketOffset);
- return 0;
- }
- p->size = n;
- /* easy case */
- if(n == 0) {
- for(f=p->first; f != nil; f=ff) {
- ff = f->next;
- fragFree(f);
- }
- p->first = p->last = nil;
- p->asize = 0;
- return 1;
- }
- /* free before offset */
- for(f=p->first; offset >= FRAGSIZE(f); f=ff) {
- p->asize -= FRAGASIZE(f);
- offset -= FRAGSIZE(f);
- ff = f->next;
- fragFree(f);
- }
- /* adjust frag */
- f->rp += offset;
- p->first = f;
- /* skip middle */
- for(; n > 0 && n > FRAGSIZE(f); f=f->next)
- n -= FRAGSIZE(f);
- /* adjust end */
- f->wp = f->rp + n;
- p->last = f;
- ff = f->next;
- f->next = nil;
- /* free after */
- for(f=ff; f != nil; f=ff) {
- p->asize -= FRAGASIZE(f);
- ff = f->next;
- fragFree(f);
- }
- return 1;
- }
- uint8_t *
- packetHeader(Packet *p, int n)
- {
- Frag *f;
- Mem *m;
- NOTFREE(p);
- if(n <= 0 || n > MaxFragSize) {
- vtSetError(EPacketSize);
- return 0;
- }
- p->size += n;
- /* try and fix in current frag */
- f = p->first;
- if(f != nil) {
- m = f->mem;
- if(n <= f->rp - m->bp)
- if(m->ref == 1 || memHead(m, f->rp, n)) {
- f->rp -= n;
- return f->rp;
- }
- }
- /* add frag to front */
- f = fragAlloc(p, n, PEnd, p->first);
- p->asize += FRAGASIZE(f);
- if(p->first == nil)
- p->last = f;
- p->first = f;
- return f->rp;
- }
- uint8_t *
- packetTrailer(Packet *p, int n)
- {
- Mem *m;
- Frag *f;
- NOTFREE(p);
- if(n <= 0 || n > MaxFragSize) {
- vtSetError(EPacketSize);
- return 0;
- }
- p->size += n;
- /* try and fix in current frag */
- if(p->first != nil) {
- f = p->last;
- m = f->mem;
- if(n <= m->ep - f->wp)
- if(m->ref == 1 || memTail(m, f->wp, n)) {
- f->wp += n;
- return f->wp - n;
- }
- }
- /* add frag to end */
- f = fragAlloc(p, n, (p->first == nil)?PMiddle:PFront, nil);
- p->asize += FRAGASIZE(f);
- if(p->first == nil)
- p->first = f;
- else
- p->last->next = f;
- p->last = f;
- return f->rp;
- }
- int
- packetPrefix(Packet *p, uint8_t *buf, int n)
- {
- Frag *f;
- int nn;
- Mem *m;
- NOTFREE(p);
- if(n <= 0)
- return 1;
- p->size += n;
- /* try and fix in current frag */
- f = p->first;
- if(f != nil) {
- m = f->mem;
- nn = f->rp - m->bp;
- if(nn > n)
- nn = n;
- if(m->ref == 1 || memHead(m, f->rp, nn)) {
- f->rp -= nn;
- n -= nn;
- memmove(f->rp, buf+n, nn);
- }
- }
- while(n > 0) {
- nn = n;
- if(nn > MaxFragSize)
- nn = MaxFragSize;
- f = fragAlloc(p, nn, PEnd, p->first);
- p->asize += FRAGASIZE(f);
- if(p->first == nil)
- p->last = f;
- p->first = f;
- n -= nn;
- memmove(f->rp, buf+n, nn);
- }
- return 1;
- }
- int
- packetAppend(Packet *p, uint8_t *buf, int n)
- {
- Frag *f;
- int nn;
- Mem *m;
- NOTFREE(p);
- if(n <= 0)
- return 1;
- p->size += n;
- /* try and fix in current frag */
- if(p->first != nil) {
- f = p->last;
- m = f->mem;
- nn = m->ep - f->wp;
- if(nn > n)
- nn = n;
- if(m->ref == 1 || memTail(m, f->wp, nn)) {
- memmove(f->wp, buf, nn);
- f->wp += nn;
- buf += nn;
- n -= nn;
- }
- }
- while(n > 0) {
- nn = n;
- if(nn > MaxFragSize)
- nn = MaxFragSize;
- f = fragAlloc(p, nn, (p->first == nil)?PMiddle:PFront, nil);
- p->asize += FRAGASIZE(f);
- if(p->first == nil)
- p->first = f;
- else
- p->last->next = f;
- p->last = f;
- memmove(f->rp, buf, nn);
- buf += nn;
- n -= nn;
- }
- return 1;
- }
- int
- packetConcat(Packet *p, Packet *pp)
- {
- NOTFREE(p);
- NOTFREE(pp);
- if(pp->size == 0)
- return 1;
- p->size += pp->size;
- p->asize += pp->asize;
- if(p->first != nil)
- p->last->next = pp->first;
- else
- p->first = pp->first;
- p->last = pp->last;
- pp->size = 0;
- pp->asize = 0;
- pp->first = nil;
- pp->last = nil;
- return 1;
- }
- uint8_t *
- packetPeek(Packet *p, uint8_t *buf, int offset, int n)
- {
- Frag *f;
- int nn;
- uint8_t *b;
- NOTFREE(p);
- if(n == 0)
- return buf;
- if(offset < 0 || offset >= p->size) {
- vtSetError(EPacketOffset);
- return 0;
- }
- if(n < 0 || offset + n > p->size) {
- vtSetError(EPacketSize);
- return 0;
- }
- /* skip up to offset */
- for(f=p->first; offset >= FRAGSIZE(f); f=f->next)
- offset -= FRAGSIZE(f);
- /* easy case */
- if(offset + n <= FRAGSIZE(f))
- return f->rp + offset;
- for(b=buf; n>0; n -= nn) {
- nn = FRAGSIZE(f) - offset;
- if(nn > n)
- nn = n;
- memmove(b, f->rp+offset, nn);
- offset = 0;
- f = f->next;
- b += nn;
- }
- return buf;
- }
- int
- packetCopy(Packet *p, uint8_t *buf, int offset, int n)
- {
- uint8_t *b;
- NOTFREE(p);
- b = packetPeek(p, buf, offset, n);
- if(b == nil)
- return 0;
- if(b != buf)
- memmove(buf, b, n);
- return 1;
- }
- int
- packetFragments(Packet *p, IOchunk *io, int nio, int offset)
- {
- Frag *f;
- int size;
- IOchunk *eio;
- NOTFREE(p);
- if(p->size == 0 || nio <= 0)
- return 0;
- if(offset < 0 || offset > p->size) {
- vtSetError(EPacketOffset);
- return -1;
- }
- for(f=p->first; offset >= FRAGSIZE(f); f=f->next)
- offset -= FRAGSIZE(f);
- size = 0;
- eio = io + nio;
- for(; f != nil && io < eio; f=f->next) {
- io->addr = f->rp + offset;
- io->len = f->wp - (f->rp + offset);
- offset = 0;
- size += io->len;
- io++;
- }
- return size;
- }
- void
- packetStats(void)
- {
- Packet *p;
- Frag *f;
- Mem *m;
- int np, nf, nsm, nbm;
- lock(&freeList.lk);
- np = 0;
- for(p=freeList.packet; p; p=p->next)
- np++;
- nf = 0;
- for(f=freeList.frag; f; f=f->next)
- nf++;
- nsm = 0;
- for(m=freeList.smallMem; m; m=m->next)
- nsm++;
- nbm = 0;
- for(m=freeList.bigMem; m; m=m->next)
- nbm++;
- fprint(2, "packet: %d/%d frag: %d/%d small mem: %d/%d big mem: %d/%d\n",
- np, freeList.npacket,
- nf, freeList.nfrag,
- nsm, freeList.nsmallMem,
- nbm, freeList.nbigMem);
- unlock(&freeList.lk);
- }
- int
- packetSize(Packet *p)
- {
- NOTFREE(p);
- if(0) {
- Frag *f;
- int size = 0;
- for(f=p->first; f; f=f->next)
- size += FRAGSIZE(f);
- if(size != p->size)
- fprint(2, "packetSize %d %d\n", size, p->size);
- assert(size == p->size);
- }
- return p->size;
- }
- int
- packetAllocatedSize(Packet *p)
- {
- NOTFREE(p);
- if(0) {
- Frag *f;
- int asize = 0;
- for(f=p->first; f; f=f->next)
- asize += FRAGASIZE(f);
- if(asize != p->asize)
- fprint(2, "packetAllocatedSize %d %d\n", asize, p->asize);
- assert(asize == p->asize);
- }
- return p->asize;
- }
- void
- packetSha1(Packet *p, uint8_t sha1[VtScoreSize])
- {
- Frag *f;
- VtSha1 *s;
- int size;
- NOTFREE(p);
- s = vtSha1Alloc();
- size = p->size;
- for(f=p->first; f; f=f->next) {
- vtSha1Update(s, f->rp, FRAGSIZE(f));
- size -= FRAGSIZE(f);
- }
- assert(size == 0);
- vtSha1Final(s, sha1);
- vtSha1Free(s);
- }
- int
- packetCmp(Packet *pkt0, Packet *pkt1)
- {
- Frag *f0, *f1;
- int n0, n1, x;
- NOTFREE(pkt0);
- NOTFREE(pkt1);
- f0 = pkt0->first;
- f1 = pkt1->first;
- if(f0 == nil)
- return (f1 == nil)?0:-1;
- if(f1 == nil)
- return 1;
- n0 = FRAGSIZE(f0);
- n1 = FRAGSIZE(f1);
- for(;;) {
- if(n0 < n1) {
- x = memcmp(f0->wp - n0, f1->wp - n1, n0);
- if(x != 0)
- return x;
- n1 -= n0;
- f0 = f0->next;
- if(f0 == nil)
- return -1;
- n0 = FRAGSIZE(f0);
- } else if (n0 > n1) {
- x = memcmp(f0->wp - n0, f1->wp - n1, n1);
- if(x != 0)
- return x;
- n0 -= n1;
- f1 = f1->next;
- if(f1 == nil)
- return 1;
- n1 = FRAGSIZE(f1);
- } else { /* n0 == n1 */
- x = memcmp(f0->wp - n0, f1->wp - n1, n0);
- if(x != 0)
- return x;
- f0 = f0->next;
- f1 = f1->next;
- if(f0 == nil)
- return (f1 == nil)?0:-1;
- if(f1 == nil)
- return 1;
- n0 = FRAGSIZE(f0);
- n1 = FRAGSIZE(f1);
- }
- }
- }
- static Frag *
- fragAlloc(Packet *p, int n, int pos, Frag *next)
- {
- Frag *f, *ef;
- Mem *m;
- /* look for local frag */
- f = &p->local[0];
- ef = &p->local[NLocalFrag];
- for(;f<ef; f++) {
- if(f->state == FragLocalFree) {
- f->state = FragLocalAlloc;
- goto Found;
- }
- }
- lock(&freeList.lk);
- f = freeList.frag;
- if(f != nil)
- freeList.frag = f->next;
- else
- freeList.nfrag++;
- unlock(&freeList.lk);
- if(f == nil) {
- f = vtMemBrk(sizeof(Frag));
- f->state = FragGlobal;
- }
- Found:
- if(n == 0)
- return f;
- if(pos == PEnd && next == nil)
- pos = PMiddle;
- m = memAlloc(n, pos);
- f->mem = m;
- f->rp = m->rp;
- f->wp = m->wp;
- f->next = next;
- return f;
- }
- static Frag *
- fragDup(Packet *p, Frag *f)
- {
- Frag *ff;
- Mem *m;
- m = f->mem;
- /*
- * m->rp && m->wp can be out of date when ref == 1
- * also, potentially reclaims space from previous frags
- */
- if(m->ref == 1) {
- m->rp = f->rp;
- m->wp = f->wp;
- }
- ff = fragAlloc(p, 0, 0, nil);
- *ff = *f;
- lock(&m->lk);
- m->ref++;
- unlock(&m->lk);
- return ff;
- }
- static void
- fragFree(Frag *f)
- {
- memFree(f->mem);
- if(f->state == FragLocalAlloc) {
- f->state = FragLocalFree;
- return;
- }
- lock(&freeList.lk);
- f->next = freeList.frag;
- freeList.frag = f;
- unlock(&freeList.lk);
- }
- static Mem *
- memAlloc(int n, int pos)
- {
- Mem *m;
- int nn;
- if(n < 0 || n > MaxFragSize) {
- vtSetError(EPacketSize);
- return 0;
- }
- if(n <= SmallMemSize) {
- lock(&freeList.lk);
- m = freeList.smallMem;
- if(m != nil)
- freeList.smallMem = m->next;
- else
- freeList.nsmallMem++;
- unlock(&freeList.lk);
- nn = SmallMemSize;
- } else {
- lock(&freeList.lk);
- m = freeList.bigMem;
- if(m != nil)
- freeList.bigMem = m->next;
- else
- freeList.nbigMem++;
- unlock(&freeList.lk);
- nn = BigMemSize;
- }
- if(m == nil) {
- m = vtMemBrk(sizeof(Mem));
- m->bp = vtMemBrk(nn);
- m->ep = m->bp + nn;
- }
- assert(m->ref == 0);
- m->ref = 1;
- switch(pos) {
- default:
- assert(0);
- case PFront:
- m->rp = m->bp;
- break;
- case PMiddle:
- /* leave a little bit at end */
- m->rp = m->ep - n - 32;
- break;
- case PEnd:
- m->rp = m->ep - n;
- break;
- }
- /* check we did not blow it */
- if(m->rp < m->bp)
- m->rp = m->bp;
- m->wp = m->rp + n;
- assert(m->rp >= m->bp && m->wp <= m->ep);
- return m;
- }
- static void
- memFree(Mem *m)
- {
- lock(&m->lk);
- m->ref--;
- if(m->ref > 0) {
- unlock(&m->lk);
- return;
- }
- unlock(&m->lk);
- assert(m->ref == 0);
- switch(m->ep - m->bp) {
- default:
- assert(0);
- case SmallMemSize:
- lock(&freeList.lk);
- m->next = freeList.smallMem;
- freeList.smallMem = m;
- unlock(&freeList.lk);
- break;
- case BigMemSize:
- lock(&freeList.lk);
- m->next = freeList.bigMem;
- freeList.bigMem = m;
- unlock(&freeList.lk);
- break;
- }
- }
- static int
- memHead(Mem *m, uint8_t *rp, int n)
- {
- lock(&m->lk);
- if(m->rp != rp) {
- unlock(&m->lk);
- return 0;
- }
- m->rp -= n;
- unlock(&m->lk);
- return 1;
- }
- static int
- memTail(Mem *m, uint8_t *wp, int n)
- {
- lock(&m->lk);
- if(m->wp != wp) {
- unlock(&m->lk);
- return 0;
- }
- m->wp += n;
- unlock(&m->lk);
- return 1;
- }
|