/* deq.c * implement deques of 12-word blocks in DECUS C * tasks can perform send/receives to operate on deques */ /* a deque is a double-ended queue * it is called a deque because of the ellision of "double", "ended" and * "queue" and because it is like a deck of cards: you can't get at the * middle but you can push/pull cards at both ends. * the operations on a deque are to push/pull from the A or the B end * of the deque: * * A end <-> X-X-X-X-X-X-X-X <-> B end * * * * deque * * * == push or pull one object here */ /* 31 deques are maintained. * all are public resources - no priveliges are enforced * except that a task can exclude all other tasks from a deque * an operation is when a task sends a packet to ...DEQ * deq guarentees to reply with exactly one packet. * the contents of the return packet depends on the operator packet * deque number 0 is special: it is returned to indicate errors and sent * to indicate "don't care" */ /* operator packets have the following format: * * +---------------------------------------------------------------+ * | operation byte | sender's 8-bit private code | * |-------------------------------| | * | 3-bit | deque number | | * | operation | [0:31] | | * | code | | | * +---------------------------------------------------------------+ * | 12 words of sender's data : meaning depends on op-code | * +---------------------------------------------------------------+ */ /* reply packets look the same: the deque number is sometimes changed * and the data changes. The sender's private byte is never changed so * senders can use this to co-relate requests and replies. */ /* opcodes look like: * * +---------------------------------------+ * | A/B | op (2 bits) | * +---------------------------------------+ * * operations are: * 00 special * if A/B = 0 then detach from the nominated deque * this decrements the usage count of the deque * when the usage count of the deque falls to 0 * then the data in the deque is lost * specifying 0 as the deque number is illegal * reply contains the deque number detached * if the reply has a zero deque number then * the detach request failed. * a detach request might fail if the owner of * the deque was not the requesting task * the data part of the request should be 0 * to allow for future foolishness * if A/B = 1 then attach to a deque * if no deque number is given then don't * care which deque number is used, * but it must be a fresh deque, not one in use. * reply deque number is 0 if deque could * not be attached else is number of deque * attached. * the first two words of the data part are * 0 or a task name. If a task name and if * currently no task owns the deque, then the * named task will now have exclusive access * to the deque. * the rest of the data part of the request * should be 0 to allow for future foolishness ** for the rest of the op-codes: each deque has two ends: ** arbitrarily named "A" and "B". Each command operates on the ** "A" end unless the A/B bit is set: then it works on the "B" end * 01 copy * return a copy of the block at the deque end * do not change the deque * ignore the data part of the request * the data part of the request should be 0 * to allow for future foolishness * such future extension might include accessing elements * which are not at the end of the deque or gathering * statistics about the deque. * return deque number of 0 if deque is empty * 10 pull * as for "copy" command but remove block if it exists * the data part of the request should be 0 * to allow for future foolishness * 11 push * catenate data part to deque end * nominating deque 0 is illegal * return deque number 0 if failed * only failure mode is "no more memory" */ /* as a convention ... don't use deque number 31. - it may mean something * special one day. In fact - keep deque numbers between 1-15. inclusive * because the high bit of the deque number may become the low bit of the * op-code in future versions! */ #include #include #define decus #define PACKETSIZE 13 #define DEQNUMBER 32 #define DATAOFFSET 1 #define EFN 0 /* request packet op-codes */ #define SPEC 0 #define COPY 1 #define PULL 2 #define PUSH 3 /* objects are organised in rings */ struct head /* object header for ring of objects */ {char *b4; /* points to previous object in ring */ char *aft; /* points to next object in ring */ } ; struct deqhed /* deque header */ {struct head hed; /* points to self if empty ring */ struct rad50 owner; /* 0 if public deque task name that exclusively owns deque */ unsigned usage; /* number of tasks attached to deque */ } ; struct object /* the things we push and pull */ {struct head hed; /* */ int data[PACKETSIZE-DATAOFFSET]; } ; /* * * a head: * * +===============+ * | | * .b4: | *---------------+ * | | | * +===============+ | * | | | * .aft: +---------------* | | * | | | | * | +===============+ | * | | * V V * "A" end "B" end * */ int tracer; /* TRUE when desperately debugging */ main(argc,argv) int argc; char **argv; {int i; /* scratch */ struct deqhed *d; /* points to particular deq(hed) we work on */ struct deqhed h[DEQNUMBER]; /* 0th element never used */ int inpack[PACKETSIZE+2]; /* incoming (request) packet */ int outpack[PACKETSIZE]; /* outgoing (reply) packet */ int b; /* TRUE if A/B bit set */ char dsw; /* dsw from exec calls */ int op; /* 2-bit op code */ int deq; /* the deq number */ struct object *o; /* scratch */ unsigned objsize; /* size in chars of object */ int trace; /* TRUE if tracing */ char ascii[7]; /* ASCII task name as string */ int printf(); objsize = sizeof(*o); trace = argc>1; tracer = argc>2; /* initialise */ for (i=31; i; i--) {d = h+i; /* d points to particular deqhed */ d->hed.b4 = d; d->hed.aft = d; d->usage = 0; d->owner.w[0] = 0; d->owner.w[1] = 0; } ; d = h; /* as a debug measure, fill deque 0 with junk */ d->hed.b4 = 1; /* bad address */ d->hed.aft = 1; d->usage = 42; d->owner.w[0] = 42; d->owner.w[1] = 42; while(1) /* repeat until we are shot */ { /* receive a request */ while ((dsw=rcst(NULL,inpack)) == IS_SET) /* ignore false alarms */ ; op = inpack[2] >> 8 & 0xFF; /* second byte of packet */ deq = op & 0x1F; op = op >> 5; b = op & 0x4; op = op & 0x3; d = h+deq; /* d points to particular deque header */ /* copy in packet to out packet */ copy(outpack,inpack+2,PACKETSIZE*sizeof(int)); if (trace) {r50toa(ascii,inpack,2); ascii[6]=0; printf("from task %s op=%d b=%d deque=%d\n",ascii,op,b,deq); wblock(inpack+2,26,printf); } ; switch (op) { case SPEC: if (b) {/* attach to deq */ if (deq==0) {for (deq=DEQNUMBER-1,d=h+DEQNUMBER; deq; deq--) {if (!(--d)->usage) {if (trace) {printf("attach:chose deque %d\n",deq); } ; break; } ; } ; } ; /* here with a deq number */ if (deq) {if (bufeq(&d->owner,4)) {if (!bufeq(inpack+2+DATAOFFSET,4)) {copy (&d->owner,inpack+2+DATAOFFSET,4); if (trace) {printf("task %s now owns deque %d\n",ascii,deq); } ; } ; } else {if (!bufcmp(&d->owner,inpack,4)) {if (trace) {r50toa(ascii,&d->owner,2); printf("but task %s owns deque %d so attach fails\n",ascii,deq); } ; deq = 0; /* private - hands off! */ } ; } ; } ; /* deq = 0 if failed */ if (deq) {d->usage++; if (trace) {printf("deque %d usage count now %d\n",deq,d->usage); } ; } ; } else /* detach */ {deqcheck(trace,&deq,&d,h,inpack); if (deq) {if (!(--(d->usage))) {/* last user detached : annihilate deque */ i = 0; while (!emptyp(d)) {aftoff(d); i++; } ; if (trace) {printf("deque %d now unused :%d objects annihilated\n",deq,i); } ; } ; if (trace) {printf("detach from deque %d leaves usage count at %d\n",deq,d->usage); } ; } ; } ; break; case COPY: deqcheck(trace,&deq,&d,h,inpack); if (deq && emptyp(d)) {if (trace) {printf("can't copy from empty deque %d\n",deq); } ; deq = 0; } ; if (deq) {o = b?d->hed.b4:d->hed.aft; if (tracer) {printf("o=%Xx d=%Xx\n",o,d); objdump(o); } ; copy(outpack+DATAOFFSET,o->data,(PACKETSIZE-DATAOFFSET)*sizeof(int)); } ; break; case PULL: deqcheck(trace,&deq,&d,h,inpack); if (deq && emptyp(d)) {if (trace) {printf("can't pull from empty deque %d\n",deq); } ; deq = 0; } ; if (deq) {o = b?d->hed.b4:d->hed.aft; if (tracer) {printf("o=%Xx d=%Xx\n",o,d); objdump(o); } ; copy(outpack+DATAOFFSET,o->data,(PACKETSIZE-DATAOFFSET)*sizeof(int)); if (b) {b4off(d); } else {aftoff(d); } ; } ; break; case PUSH: deqcheck(trace,&deq,&d,h,inpack); if (deq && !(b?b4on(d,objsize):afton(d,objsize))) {if (trace) {printf("no room to push onto %c end of deque %d\n",b?'B':'A',deq); } ; deq = 0; /* no room */ } ; if (deq) {o = b?d->hed.b4:d->hed.aft; if (tracer) {printf("o=%Xx d=%Xx\n",o,d); } ; copy(o->data,inpack+2+DATAOFFSET,(PACKETSIZE-DATAOFFSET)*sizeof(int)); if (tracer) {objdump(o); } ; } ; break; default: if (trace) {printf("impossible op = %d\n",op); } ; deq = 0; break; } ; outpack[0] = outpack[0] & 0xE0FF | deq<<8 ; if (trace) {wblock(outpack,26,printf); printf("\n"); } ; dsw = sdat(inpack,outpack,EFN); if (dsw!=IS_SUC) printf("\7dsw of sdat =%oo\n",dsw); dsw = ustp(inpack); if (dsw!=IS_SUC && dsw !=IE_ITS) printf("\7dsw of ustp =%oo\n",dsw); } ; } deqcheck(trace,deqp,dp,hp,inpack) /* check deq access rights */ int trace; /* TRUE if tracing */ int *deqp; /* points to deq */ struct deqhed **dp; /* points to d */ struct deqhed hp[DEQNUMBER]; int inpack[PACKETSIZE+2]; {int deq; struct deqhed *d; char ascii[7]; /* ASCII task name string */ deq = *deqp; if (trace) {r50toa(ascii,inpack,2); ascii[6]=0; printf("checking access of task %s to deque %d\n",ascii,deq); } ; if (deq) {d = hp+deq; if (bufeq(&d->owner,4)) {if (!d->usage) {if (trace) {printf("access denied: no task owns deque but usage count is zero\n"); } ; deq = 0; } ; } else {if (!bufcmp(&d->owner,inpack,4)) {if (trace) {r50toa(ascii,&d->owner,2); printf("access denied: task %s owns deque %d\n",ascii,deq); } ; deq = 0; } ; } ; } ; *dp = d; *deqp = deq; /* zero if failed */ if (trace && deq) {printf("access granted\n"); } ; } int emptyp(d) struct deqhed *d; {return(d->hed.b4 == &d->hed); } b4off(d) struct deqhed *d; {struct head *hp,*hhp,*hhhp; hp = &d->hed; hhp = hp->b4; hhhp = hhp->b4; if (tracer) {printf("aoff: d=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,hp,hhp,hhhp); printf("aoff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; hp->b4 = hhhp; hhhp->aft = hp; if (tracer) {printf("aoff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; mfree(hhp); } aftoff(d) struct deqhed *d; {struct head *hp,*hhp,*hhhp; hp = &d->hed; hhp = hp->aft; hhhp = hhp->aft; if (tracer) {printf("boff: d=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,hp,hhp,hhhp); printf("boff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; hp->aft = hhhp; hhhp->b4 = hp; if (tracer) {printf("boff: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; mfree(hhp); } int b4on(d,size) struct deqhed *d; {struct head *hp,*hhp,*hhhp; hp = &d->hed; hhhp = hp->b4; hhp = malloc(size); if (tracer) {printf("aon: d=%Xx size=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,size,hp,hhp,hhhp); printf("aon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; if (!hhp) return(0); hhp->b4 = hhhp; hhp->aft = hp; hhhp->aft = hhp; hp->b4 = hhp; if (tracer) {printf("aon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; return (1); } int afton(d,size) struct deqhed *d; {struct head *hp,*hhp,*hhhp; hp = &d->hed; hhhp = hp->aft; hhp = malloc(size); if (tracer) {printf("bon: d=%Xx size=%Xx hp=%Xx hhp=%Xx hhhp=%Xx\n",d,size,hp,hhp,hhhp); printf("bon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; if (!hhp) return(0); hhp->aft = hhhp; hhp->b4 = hp; hhhp->b4 = hhp; hp->aft = hhp; if (tracer) {printf("bon: hp->b4=%Xx hp->aft=%Xx hhp->b4=%Xx hhp->aft=%Xx hhhp->b4=%Xx hhhp->aft=%Xx\n" ,hp->b4,hp->aft,hhp->b4,hhp->aft,hhhp->b4,hhhp->aft); } ; return (1); } int bufcmp(a,b,len) char *a; char *b; unsigned len; {while (len--) if (*a++!=*b++) return (*--a<*--b?-1:1); return(0); } int bufeq(a,len) char *a; unsigned len; {int r; r = 1; while (len--) if (*a++) {r=0; break;} if (tracer) {printf("bufeq: returns %d\n",r); } ; return(r); } objdump(o) struct object *o; {int printf(); printf("dumping object at address %Xx: b4=%Xx aft=%Xx\n",o,o->hed.b4,o->hed.aft); wblock(o->data,(PACKETSIZE-DATAOFFSET)*2,printf); } wblock(buf,len,pf) char *buf; int len; int (*pf)(); {int max; int i; while (len) {max = len>8 ? 8 : len; for (i = 0; i