From: Simon Wilkinson Date: Mon, 25 Oct 2010 10:26:51 +0000 (+0100) Subject: opr: Add new queue implementation X-Git-Tag: openafs-devel-1_7_1~1112 X-Git-Url: http://git.openafs.org/?p=openafs.git;a=commitdiff_plain;h=acfc61eca83ecc895e51ae512c1919e7997a560e;hp=e8d8a2240a57f9f4a11ee45b60c229d3f8447b86 opr: Add new queue implementation Add a new queue implementation for OpenAFS. This has a similar calling form as the current RX queue implementation, but is implementated using type safe functions, and supports structures with multiple queue headers. This permits threading a structure onto multiple queues at the same time. The eventual intention is that this queue implementation will replace both rx_queue and the Unix cache manager afs_q. Change-Id: I8f815872b017a85eb52a6e6451cdcee3eb869519 Reviewed-on: http://gerrit.openafs.org/3139 Reviewed-by: Derrick Brashear Tested-by: Derrick Brashear --- diff --git a/Makefile.in b/Makefile.in index 9ef9f80..423956b 100644 --- a/Makefile.in +++ b/Makefile.in @@ -109,7 +109,7 @@ packages: dest echo Not building packages for ${SYS_NAME} ;; \ esac -${TOP_INCDIR}/afs ${TOP_INCDIR}/rx ${TOP_INCDIR}/hcrypto ${TOP_LIBDIR} ${TOP_JLIBDIR}: +${TOP_INCDIR}/afs ${TOP_INCDIR}/rx ${TOP_INCDIR}/hcrypto ${TOP_INCDIR}/opr ${TOP_LIBDIR} ${TOP_JLIBDIR}: mkdir -p $@ install_dirs: force @@ -135,7 +135,7 @@ dest_dirs: force mkdir -p ${DEST}/root.server/etc mkdir -p ${DEST}/root.server/usr/afs/bin -prelude: ${TOP_INCDIR}/afs ${TOP_INCDIR}/rx ${TOP_INCDIR}/hcrypto ${TOP_LIBDIR} +prelude: ${TOP_INCDIR}/afs ${TOP_INCDIR}/rx ${TOP_INCDIR}/hcrypto ${TOP_INCDIR}/opr ${TOP_LIBDIR} project: cmd comerr diff --git a/src/config/NTMakefile b/src/config/NTMakefile index e9ce7ef..c34f811 100644 --- a/src/config/NTMakefile +++ b/src/config/NTMakefile @@ -424,6 +424,9 @@ idirs: doclink ! IF (!EXIST($(DESTDIR)\include\hcrypto)) $(MKDIR) $(DESTDIR)\include\hcrypto ! ENDIF +! IF (!EXIST($(DESTDIR)\include\opr)) + $(MKDIR) $(DESTDIR)\include\opr +! ENDIF ! IF (!EXIST($(DESTDIR)\include\rx)) $(MKDIR) $(DESTDIR)\include\rx ! ENDIF diff --git a/src/config/NTMakefile.amd64_w2k b/src/config/NTMakefile.amd64_w2k index 8f01027..05c714a 100644 --- a/src/config/NTMakefile.amd64_w2k +++ b/src/config/NTMakefile.amd64_w2k @@ -407,6 +407,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\rx}.h: $(COPY) $< $(DESTDIR)\include\rx +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $< $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\des}.h: $(COPY) $< $(DESTDIR)\include @@ -428,6 +431,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\rx}.h: $(COPY) $(*B).h $(DESTDIR)\include\rx +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $(*B).h $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\des}.h: $(COPY) $(*B).h $(DESTDIR)\include diff --git a/src/config/NTMakefile.i386_nt40 b/src/config/NTMakefile.i386_nt40 index 3046196..4c0f63d 100644 --- a/src/config/NTMakefile.i386_nt40 +++ b/src/config/NTMakefile.i386_nt40 @@ -368,6 +368,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\rx}.h: $(COPY) $< $(DESTDIR)\include\rx +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $< $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\des}.h: $(COPY) $< $(DESTDIR)\include @@ -389,6 +392,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\rx}.h: $(COPY) $(*B).h $(DESTDIR)\include\rx +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $(*B).h $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\des}.h: $(COPY) $(*B).h $(DESTDIR)\include diff --git a/src/config/NTMakefile.i386_w2k b/src/config/NTMakefile.i386_w2k index c294cee..be3b3fb 100644 --- a/src/config/NTMakefile.i386_w2k +++ b/src/config/NTMakefile.i386_w2k @@ -416,6 +416,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\rx}.h: $(COPY) $< $(DESTDIR)\include\rx +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $< $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\des}.h: $(COPY) $< $(DESTDIR)\include @@ -434,6 +437,9 @@ CPP2OBJ = $(C2OBJ) .h.{$(DESTDIR)\include\afs}.h: $(COPY) $(*B).h $(DESTDIR)\include\afs +.h.{$(DESTDIR)\include\opr}.h: + $(COPY) $(*B).h $(DESTDIR)\include\opr + .h.{$(DESTDIR)\include\rx}.h: $(COPY) $(*B).h $(DESTDIR)\include\rx diff --git a/src/util/Makefile.in b/src/util/Makefile.in index 80cb98c..00f8bad 100644 --- a/src/util/Makefile.in +++ b/src/util/Makefile.in @@ -44,7 +44,8 @@ includes = \ ${TOP_INCDIR}/afs/work_queue_types.h \ ${TOP_INCDIR}/afs/thread_pool.h \ ${TOP_INCDIR}/afs/thread_pool_types.h \ - ${TOP_INCDIR}/afs/tabular_output.h + ${TOP_INCDIR}/afs/tabular_output.h \ + ${TOP_INCDIR}/opr/queue.h all: ${includes} \ ${TOP_LIBDIR}/util.a \ @@ -118,6 +119,12 @@ ${TOP_INCDIR}/afs/thread_pool_types.h: ${srcdir}/thread_pool_types.h ${TOP_INCDIR}/afs/tabular_output.h: ${srcdir}/tabular_output.h ${INSTALL_DATA} $? $@ +${TOP_INCDIR}/potpourri.h: ${srcdir}/potpourri.h + ${INSTALL_DATA} $? $@ + +${TOP_INCDIR}/opr/queue.h: ${srcdir}/queue.h + ${INSTALL_DATA} $? $@ + ${TOP_LIBDIR}/util.a: util.a ${INSTALL_DATA} $? $@ diff --git a/src/util/NTMakefile b/src/util/NTMakefile index 9855c61..e4f14cd 100644 --- a/src/util/NTMakefile +++ b/src/util/NTMakefile @@ -15,6 +15,7 @@ INCFILEDIR = $(DESTDIR)\include\afs # header file install directory INCFILES =\ $(DESTDIR)\include\dirent.h \ + $(DESTDIR)\include\opr\queue.h \ $(INCFILEDIR)\afsutil.h \ $(INCFILEDIR)\afs_assert.h \ $(INCFILEDIR)\errors.h \ diff --git a/src/util/queue.h b/src/util/queue.h new file mode 100644 index 0000000..44ac5d5 --- /dev/null +++ b/src/util/queue.h @@ -0,0 +1,229 @@ +/* + * Copyright (c) 2010 Your File System Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* A better queue implementation. + * + * This differs from the original queue implementation in that that would + * only allow a structure to be threaded onto a single queue. This permits + * a given object to be on multiple queues, providing that each queue has + * a place in the structure definition. + */ + +#ifndef OPENAFS_OPR_QUEUE_H +#define OPENAFS_OPR_QUEUE_H 1 + +#ifndef KERNEL +#include +#else +#ifndef NULL +#define NULL (void *)0 +#endif +#endif + +struct opr_queue { + struct opr_queue *next; + struct opr_queue *prev; +}; + +#define opr_queue_Scan(head, cursor) \ + cursor = (head)->next; cursor != (head); cursor = cursor->next + +#define opr_queue_ScanSafe(head, cursor, store) \ + cursor = (head)->next, store = cursor->next; \ + cursor != (head); \ + cursor = store, store = store->next + +#define opr_queue_ScanBackwards(head, cursor) \ + cursor = (head)->prev; cursor != (head); cursor = cursor->prev + +#define opr_queue_ScanBackwardsSafe(head, cursor, store) \ + cursor = (head)->prev, store = cursor->prev; \ + cursor != (head); \ + cursor = store, store = store->prev + +static_inline void +opr_queue_Zero(struct opr_queue *q) { + q->prev = q->next = NULL; +} + +static_inline void +opr_queue_Init(struct opr_queue *q) { + q->prev = q->next = q; +} + +static_inline void +opr_queue_add(struct opr_queue *element, + struct opr_queue *before, struct opr_queue *after) { + after->prev = element; + element->next = after; + element->prev = before; + before->next = element; +} + +static_inline void +opr_queue_Append(struct opr_queue *queue, struct opr_queue *element) { + opr_queue_add(element, queue->prev, queue); +} + +static_inline void +opr_queue_Prepend(struct opr_queue *queue, struct opr_queue *element) { + opr_queue_add(element, queue, queue->next); +} + +static_inline void +opr_queue_InsertBefore(struct opr_queue *exist, struct opr_queue *adding) { + /* This may seem back to front, but take a list A, B, C where we want + * to add 1 before B. So, we're adding 1 with A the element before, + * and B the element after, hence the following: */ + opr_queue_add(adding, exist->prev, exist); +} + +static_inline void +opr_queue_InsertAfter(struct opr_queue *exist, struct opr_queue *adding) { + opr_queue_add(adding, exist, exist->next); +} + +static_inline void +opr_queue_Remove(struct opr_queue *element) { + element->next->prev = element->prev; + element->prev->next = element->next; + element->prev = NULL; + element->next = NULL; +} + +static_inline int +opr_queue_IsEmpty(struct opr_queue *q) { + return (q->prev == q); +} + +static_inline int +opr_queue_IsOnQueue(struct opr_queue *q) { + return (q->prev != NULL); +} + +static_inline int +opr_queue_IsEnd(struct opr_queue *q, struct opr_queue *cursor) { + return (cursor->next == q); +} + +static_inline int +opr_queue_Count(struct opr_queue *q) { + struct opr_queue *cursor; + int n = 0; + + for (opr_queue_Scan(q, cursor)) { + n++; + } + return n; +} + +/* Remove the members before pivot from Q1, and append them to Q2 */ + +static_inline void +opr_queue_SplitBeforeAppend(struct opr_queue *q1, struct opr_queue *q2, + struct opr_queue *pivot) { + + if (q1 == pivot->prev) + return; + /* Add ourselves to the end of list 2 */ + q2->prev->next = q1->next; /* end of list 2, is now the start of list 1 */ + q1->next->prev = q2->prev; + pivot->prev->next = q2; /* entry before the pivot is it at end of q2 */ + q2->prev = pivot->prev; + + /* Pull ourselves out of list q1. */ + q1->next = pivot; + pivot->prev = q1; +} + +/* Remove the members after the pivot from Q1, and prepend them onto Q2 */ +static_inline void +opr_queue_SplitAfterPrepend(struct opr_queue *q1, struct opr_queue *q2, + struct opr_queue *pivot) { + + if (q1 == pivot->next) + return; + + /* start of q2 has last element of q1 before it */ + q2->next->prev = q1->prev; + q1->prev->next = q2->next; + /* item that we're breaking at (pivot->next) is at start of q2 */ + q2->next = pivot->next; + pivot->next->prev = q2; + + /* Q1 now ends after pivot */ + pivot->next = q1; + q1->prev = pivot; +} + +static_inline void +opr_queue_SpliceAppend(struct opr_queue *target, struct opr_queue *source) +{ + + if (source->next == source) + return; + + /* Stick the contents of source onto the end of target */ + target->prev->next = source->next; + source->next->prev = target->prev; + source->prev->next = target; + target->prev = source->prev; + + /* Reinitialise source */ + source->next = source->prev = source; +} + +static_inline void +opr_queue_SplicePrepend(struct opr_queue *target, struct opr_queue *source) +{ + + if (source->next == source) + return; + + /* Contents of source go onto the beginning of target */ + target->next->prev = source->prev; + source->prev->next = target->next; + source->next->prev = target; + target->next = source->next; + + /* Reinitialise source */ + source->next = source->prev = source; +} + +#define opr_queue_Entry(queue, structure, member) \ + ((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member))) + +#define opr_queue_First(queue, structure, member) \ + opr_queue_Entry((queue)->next, structure, member) + +#define opr_queue_Last(queue, structure, member) \ + opr_queue_Entry((queue)->prev, structure, member) + +#define opr_queue_Next(entry, structure, member) \ + opr_queue_Entry((entry)->next, structure, member) + +#define opr_queue_Prev(entry, structure, member) \ + opr_queue_Entry((entry)->prev, structure, member) + +#endif diff --git a/tests/TESTS b/tests/TESTS index 8f98f5e..baa2dcc 100644 --- a/tests/TESTS +++ b/tests/TESTS @@ -1,3 +1,4 @@ util/ktime util/exec-alt +util/queues auth/superuser diff --git a/tests/util/Makefile.in b/tests/util/Makefile.in index df129e5..c760c58 100644 --- a/tests/util/Makefile.in +++ b/tests/util/Makefile.in @@ -9,7 +9,7 @@ MODULE_CFLAGS = -I$(srcdir)/.. LIBS = ../tap/libtap.a $(abs_top_builddir)/lib/util.a -tests = ktime-t exec-alt-t +tests = ktime-t exec-alt-t queues-t all check test tests: $(tests) @@ -19,6 +19,9 @@ ktime-t: ktime-t.o $(LIBS) exec-alt-t: exec-alt-t.o $(LIBS) $(AFS_LDRULE) exec-alt-t.o $(LIBS) $(XLIBS) +queues-t: queues-t.o + $(AFS_LDRULE) queues-t.o ../tap/libtap.a $(XLIBS) + install: clean distclean: diff --git a/tests/util/queues-t.c b/tests/util/queues-t.c new file mode 100644 index 0000000..e0ce888 --- /dev/null +++ b/tests/util/queues-t.c @@ -0,0 +1,122 @@ +#include +#include + +#include + +#include + +#include + + +struct charqueue { + struct opr_queue entry; + char item; +}; + + +struct charqueue * +newEntry(char string) +{ + struct charqueue *entry; + + entry=malloc(sizeof(struct charqueue)); + entry->item=string; + return(entry); +} + +char * +queueAsString(struct opr_queue *head) { + static char items[255]; + struct opr_queue *cursor; + int pos = 0; + + for(opr_queue_Scan(head, cursor)) { + items[pos] = opr_queue_Entry(cursor, struct charqueue, entry)->item; + pos++; + if (pos==254) + break; + } + items[pos]='\0'; + + return items; +} + +void +stringIntoQueue(char *string, struct opr_queue *q) { + int i; + + i = 0; + while (string[i]!='\0') { + opr_queue_Append(q, &(newEntry(string[i])->entry)); + i++; + } +} + +int +main(void) +{ + struct opr_queue q1, q2, *cursor; + + plan(12); + + opr_queue_Init(&q1); + opr_queue_Init(&q2); + + opr_queue_Append(&q1, &(newEntry('A')->entry)); + opr_queue_Append(&q1, &(newEntry('B')->entry)); + opr_queue_Append(&q1, &(newEntry('C')->entry)); + is_string(queueAsString(&q1), "ABC", "Append works as expected"); + + opr_queue_Prepend(&q1, &(newEntry('D')->entry)); + opr_queue_Prepend(&q1, &(newEntry('E')->entry)); + is_string(queueAsString(&q1), "EDABC", "Prepend works"); + + opr_queue_Append(&q2, &(newEntry('1')->entry)); + opr_queue_Append(&q2, &(newEntry('2')->entry)); + + opr_queue_SpliceAppend(&q1, &q2); + is_string(queueAsString(&q1), "EDABC12", "SpliceAppend works"); + ok(opr_queue_IsEmpty(&q2), + "IsEmpty works (and splice empties queues)"); + + opr_queue_Append(&q2, &(newEntry('8')->entry)); + opr_queue_Append(&q2, &(newEntry('9')->entry)); + is_string(queueAsString(&q2), "89", "Append works again"); + + opr_queue_SplicePrepend(&q1, &q2); + is_string(queueAsString(&q1), "89EDABC12", "SplicePrepend works"); + + /* Now for some trickier stuff */ + stringIntoQueue("XYZ", &q2); + + /* Find the A in the string above */ + for (opr_queue_Scan(&q1, cursor)) { + if (opr_queue_Entry(cursor, struct charqueue, entry)->item == 'A') + break; + } + + opr_queue_InsertBefore(cursor, &(newEntry('M')->entry)); + is_string("89EDMABC12", queueAsString(&q1), + "InsertBefore functions correctly"); + opr_queue_SplitBeforeAppend(&q1, &q2, cursor); + is_string("ABC12", queueAsString(&q1), + "SplitBefore leaves old queue in correct state"); + is_string("XYZ89EDM", queueAsString(&q2), + "SplitBefore correctly appends to new queue"); + + /* Find the 9 in q2 */ + for (opr_queue_Scan(&q2, cursor)) { + if (opr_queue_Entry(cursor, struct charqueue, entry)->item == '9') + break; + } + opr_queue_InsertAfter(cursor, &(newEntry('N')->entry)); + is_string("XYZ89NEDM", queueAsString(&q2), "InsertAfter"); + + opr_queue_SplitAfterPrepend(&q2, &q1, cursor); + is_string("NEDMABC12", queueAsString(&q1), "SplitAfterPrepend Q1"); + is_string("XYZ89", queueAsString(&q2), "SplitAfterPrepend Q2"); + + return 0; +} + +