From 7311509d11a0986a52967c1195f4cfb8bce2b332 Mon Sep 17 00:00:00 2001 From: KyoungSoo Park Date: Mon, 22 Oct 2007 17:14:06 +0000 Subject: [PATCH] - fixed the slow memory leak problem. - added memory leak debugging code - up the RPM version --- Makefile | 2 +- codemux.c | 37 ++-- codemux.spec | 2 +- codemuxlib.c | 254 ++++++++++++++++++++++- codemuxlib.h | 31 ++- debug.c | 177 ++++++++++++++++ debug.h | 49 ++--- queue.h | 562 +++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 1057 insertions(+), 57 deletions(-) create mode 100644 debug.c create mode 100644 queue.h diff --git a/Makefile b/Makefile index 83cb0f3..2024ca4 100644 --- a/Makefile +++ b/Makefile @@ -8,7 +8,7 @@ all: ${TARGS} clean: rm -f ${TARGS} *.o *~ -SHARED_OBJ = codemuxlib.o +SHARED_OBJ = codemuxlib.o debug.o CODEMUX_OBJ = codemux.o ${SHARED_OBJ} diff --git a/codemux.c b/codemux.c index 34ffc30..5ba4b01 100644 --- a/codemux.c +++ b/codemux.c @@ -14,13 +14,11 @@ #include #include #include "codemuxlib.h" - -#define DEBUG 0 +#include "debug.h" #ifdef DEBUG -#define TRACE(fmt, msg...) fprintf(stderr, "[%s,%d] " fmt, __FUNCTION__, __LINE__, ##msg) -#else -#define TRACE(fmt, msg...) (void)0 +HANDLE hdebugLog; +int defaultTraceSync; #endif #define CONF_FILE "/etc/codemux/codemux.conf" @@ -174,14 +172,14 @@ GetSliceXids(void) int xid; if ((temp = strchr(line, ':')) == NULL) - continue; /* weird line */ + goto next_line; /* weird line */ *temp = '\0'; /* terminate slice name */ temp++; if ((temp = strchr(temp+1, ':')) == NULL) - continue; /* weird line */ + goto next_line; /* weird line */ if ((xid = atoi(temp+1)) < 1) - continue; /* weird xid */ - + goto next_line; /* weird xid */ + /* we've got a slice name and xid, let's try to match */ for (i = 0; i < numSlices; i++) { if (slices[i].si_xid == 0 && @@ -190,6 +188,9 @@ GetSliceXids(void) break; } } + next_line: + if (line) + xfree(line); } /* assume service 0 is the root service, and don't check it since @@ -246,11 +247,11 @@ WhichSlicePos(char *slice) if (numSlices >= numSlicesAlloc) { numSlicesAlloc = MAX(8, numSlicesAlloc * 2); - slices = realloc(slices, numSlicesAlloc * sizeof(SliceInfo)); + slices = xrealloc(slices, numSlicesAlloc * sizeof(SliceInfo)); } memset(&slices[numSlices], 0, sizeof(SliceInfo)); - slices[numSlices].si_sliceName = strdup(slice); + slices[numSlices].si_sliceName = xstrdup(slice); numSlices++; return(numSlices-1); } @@ -290,7 +291,7 @@ ReadConfFile(void) ServiceSig serv; int port; if (line != NULL) - free(line); + xfree(line); if ((line = GetNextLine(f)) == NULL) break; @@ -317,7 +318,7 @@ ReadConfFile(void) } if (num >= numAlloc) { numAlloc = MAX(numAlloc * 2, 8); - servs = realloc(servs, numAlloc * sizeof(ServiceSig)); + servs = xrealloc(servs, numAlloc * sizeof(ServiceSig)); } serv.ss_slicePos = WhichSlicePos(serv.ss_slice); if (slices[serv.ss_slicePos].si_inUse == 0 && @@ -338,10 +339,10 @@ ReadConfFile(void) } for (i = 0; i < numServices; i++) { - free(serviceSig[i].ss_host); - free(serviceSig[i].ss_slice); + xfree(serviceSig[i].ss_host); + xfree(serviceSig[i].ss_slice); } - free(serviceSig); + xfree(serviceSig); serviceSig = servs; numServices = num; confFileReadTime = statBuf.st_mtime; @@ -680,7 +681,7 @@ SocketReadyToRead(int fd) } if ((fb = si->si_readBuf) == NULL) { - fb = si->si_readBuf = calloc(1, sizeof(FlowBuf)); + fb = si->si_readBuf = xcalloc(1, sizeof(FlowBuf)); fb->fb_refs = 1; if (si->si_peerFd >= 0) { sockInfo[si->si_peerFd].si_writeBuf = fb; @@ -689,7 +690,7 @@ SocketReadyToRead(int fd) } if (fb->fb_buf == NULL) - fb->fb_buf = malloc(FB_ALLOCSIZE); + fb->fb_buf = xmalloc(FB_ALLOCSIZE); /* determine read buffer size - if 0, then block reads and return */ if ((spaceLeft = FB_SIZE - fb->fb_used) <= 0) { diff --git a/codemux.spec b/codemux.spec index 5e9eb8f..7196e64 100644 --- a/codemux.spec +++ b/codemux.spec @@ -1,6 +1,6 @@ %define name codemux %define version 0.1 -%define release 6%{?pldistro:.%{pldistro}}%{?date:.%{date}} +%define release 7%{?pldistro:.%{pldistro}}%{?date:.%{date}} Summary: CoDemux - HTTP port DeMux Name: %{name} diff --git a/codemuxlib.c b/codemuxlib.c index 1f88633..206c08f 100644 --- a/codemuxlib.c +++ b/codemuxlib.c @@ -10,8 +10,8 @@ #include #include #include -#include "debug.h" #include "codemuxlib.h" +#include "debug.h" /*-----------------------------------------------------------------*/ static char * @@ -271,3 +271,255 @@ NiceExitBack(int val, char *reason, char *file, int line) fprintf(stderr, "%s", buf); exit(val); } +/*-----------------------------------------------------------------*/ +/* Logging & Trace support */ + +/* buffer threshold : when the size hits this value, it flushes its content + to the file */ +#define LOG_BYTES_THRESHOLD (32*1024) + +/* this flag indicates that it preserves the base file name for the current + one, and changes its name when it actually closes it off */ +#define CHANGE_FILE_NAME_ON_SAVE 0x01 + +/* size of the actual log buffer */ +#define LOG_BYTES_MAX (2*LOG_BYTES_THRESHOLD) + +/* log/trace book keeping information */ +typedef struct ExtendedLog { + char buffer[LOG_BYTES_MAX]; /* 64 KB */ + int bytes; /* number of bytes written */ + int filesize; /* number of bytes written into this file so far */ + int fd; /* file descriptor */ + char* sig; /* base file name */ + int flags; /* flags */ + time_t nextday; +} ExtendedLog, *PExtendedLog; + +/* maximum single file size */ +int maxSingleLogSize = 100 * (1024*1024); + +static time_t +GetNextLogFileName(char* file, int size, const char* sig) +{ +#define COMPRESS_EXT1 ".bz2" +#define COMPRESS_EXT2 ".gz" + + struct tm cur_tm; + time_t cur_t; + int idx = 0; + + cur_t = time(NULL); + cur_tm = *gmtime(&cur_t); + + for (;;) { + /* check if .bz2 exists */ + snprintf(file, size, "%s.%04d%02d%02d_%03d%s", + sig, cur_tm.tm_year+1900, cur_tm.tm_mon+1, cur_tm.tm_mday, + idx, COMPRESS_EXT1); + + if (access(file, F_OK) == 0) { + idx++; + continue; + } + + /* check if .gz exists */ + snprintf(file, size, "%s.%04d%02d%02d_%03d%s", + sig, cur_tm.tm_year+1900, cur_tm.tm_mon+1, cur_tm.tm_mday, + idx++, COMPRESS_EXT2); + + if (access(file, F_OK) == 0) + continue; + + /* strip the extension and see if the (uncompressed) file exists */ + file[strlen(file) - sizeof(COMPRESS_EXT2) + 1] = 0; + if (access(file, F_OK) != 0) + break; + } + + /* calculate & return the next day */ + cur_t -= (3600*cur_tm.tm_hour + 60*cur_tm.tm_min + cur_tm.tm_sec); + return cur_t + 60*60*24; + +#undef COMPRESS_EXT1 +#undef COMPRESS_EXT2 +} +/*-----------------------------------------------------------------*/ +static void +FlushBuffer(HANDLE file) +{ + /* write data into the file */ + ExtendedLog* pel = (ExtendedLog *)file; + int written; + + if (pel == NULL || pel->fd < 0) + return; + + if ((written = write(pel->fd, pel->buffer, pel->bytes)) > 0) { + pel->bytes -= written; + + /* if it hasn't written all data, then we need to move memory */ + if (pel->bytes > 0) + memmove(pel->buffer, pel->buffer + written, pel->bytes); + pel->buffer[pel->bytes] = 0; + pel->filesize += written; + } + + /* if the filesize is bigger than maxSignleLogSize, then close it off */ + if (pel->filesize >= maxSingleLogSize) + OpenLogF(file); +} + +/*-----------------------------------------------------------------*/ +HANDLE +CreateLogFHandle(const char* signature, int change_file_name_on_save) +{ + ExtendedLog* pel; + char *temp; + + /* check if the file can be created */ + if ((temp = strrchr(signature, '/')) != NULL) { + int dirlen = temp - signature + 1; + char pardir[dirlen+1]; + + memcpy(pardir, signature, dirlen); + pardir[dirlen] = 0; + if (access(pardir, W_OK) != 0) + return NULL; + } else { + /* assume it's the current directory */ + if (access("./", W_OK) != 0) + return NULL; + } + + if ((pel = (ExtendedLog *)xcalloc(1, sizeof(ExtendedLog))) == NULL) + NiceExit(-1, "failed"); + + pel->fd = -1; + pel->sig = xstrdup(signature); + if (pel->sig == NULL) + NiceExit(-1, "signature copying failed"); + if (change_file_name_on_save) + pel->flags |= CHANGE_FILE_NAME_ON_SAVE; + + return pel; +} + + +/*-----------------------------------------------------------------*/ +int +OpenLogF(HANDLE file) +{ + char filename[1024]; + ExtendedLog* pel = (ExtendedLog *)file; + + if (pel == NULL) + return -1; + + if (pel->fd != -1) + close(pel->fd); + + pel->nextday = GetNextLogFileName(filename, sizeof(filename), pel->sig); + + /* change the file name only at saving time + use pel->sig as current file name */ + if (pel->flags & CHANGE_FILE_NAME_ON_SAVE) { + if (access(pel->sig, F_OK) == 0) + rename(pel->sig, filename); + strcpy(filename, pel->sig); + } + + /* file opening */ + if ((pel->fd = open(filename, O_RDWR | O_CREAT | O_APPEND, + S_IRUSR | S_IWUSR)) == -1) { + char errMessage[2048]; + sprintf(errMessage, "couldn't open the extended log file %s\n", filename); + NiceExit(-1, errMessage); + } + + /* reset the file size */ + pel->filesize = 0; + return 0; +} + +/*-----------------------------------------------------------------*/ +int +WriteLog(HANDLE file, const char* data, int size, int forceFlush) +{ + ExtendedLog* pel = (ExtendedLog *)file; + + /* if an error might occur, then stop here */ + if (pel == NULL || pel->fd < 0 || size > LOG_BYTES_MAX) + return -1; + + if (data != NULL) { + /* flush the previous data, if this data would overfill the buffer */ + if (pel->bytes + size >= LOG_BYTES_MAX) + FlushBuffer(file); + + /* write into the buffer */ + memcpy(pel->buffer + pel->bytes, data, size); + pel->bytes += size; + } + + /* need to flush ? */ + if ((forceFlush && (pel->bytes > 0)) || (pel->bytes >= LOG_BYTES_THRESHOLD)) + FlushBuffer(file); + + return 0; +} +/*-----------------------------------------------------------------*/ +void +DailyReopenLogF(HANDLE file) +{ + /* check if current file is a day long, + opens another for today's file */ + ExtendedLog* pel = (ExtendedLog *)file; + + if (pel && (time(NULL) >= pel->nextday)) { + FlushLogF(file); /* flush */ + OpenLogF(file); /* close previous one & reopen today's */ + } +} +/*-----------------------------------------------------------------*/ +int +HandleToFileNo(HANDLE file) +{ + ExtendedLog* pel = (ExtendedLog *)file; + + return (pel != NULL) ? pel->fd : -1; +} +/*-----------------------------------------------------------------*/ +unsigned int +HashString(const char *name, unsigned int hash, int endOnQuery, + int skipLastIfDot) +{ + /* if endOnQuery, we stop the hashing when we hit the question mark. + if skipLastIfDot, we check the last component of the path to see + if it includes a dot, and it so, we skip it. if both are specified, + we first try the query, and if that exists, we don't trim the path */ + + int i; + int len; + char *temp; + + if (name == NULL) + return 0; + + len = strlen(name); + if (endOnQuery && (temp = strchr(name, '?')) != NULL) + len = temp - name; + else if (skipLastIfDot) { + /* first, find last component by searching backward */ + if ((temp = strrchr(name, '/')) != NULL) { + /* now search forward for the dot */ + if (strchr(temp, '.') != NULL) + len = temp - name; + } + } + + for (i = 0; i < len; i ++) + hash += (_rotl(hash, 19) + name[i]); + + return hash; +} diff --git a/codemuxlib.h b/codemuxlib.h index b954e31..5911620 100644 --- a/codemuxlib.h +++ b/codemuxlib.h @@ -16,19 +16,32 @@ #include "appdef.h" +typedef void* HANDLE; + /* stripped version of applib.c for codemux */ -char *GetNextLine(FILE *file); -int WordCount(char *buf); -char *GetField(const char *start, int whichField); -char *GetWord(const char *start, int whichWord); -int DoesDotlessSuffixMatch(char *start, int len, char *suffix); -int CreatePrivateAcceptSocket(int portNum, int nonBlocking); -char *StrdupLower(const char *orig); -void StrcpyLower(char *dest, const char *src); +extern char *GetNextLine(FILE *file); +extern int WordCount(char *buf); +extern char *GetField(const char *start, int whichField); +extern char *GetWord(const char *start, int whichWord); +extern int DoesDotlessSuffixMatch(char *start, int len, char *suffix); +extern int CreatePrivateAcceptSocket(int portNum, int nonBlocking); +extern char *StrdupLower(const char *orig); +extern void StrcpyLower(char *dest, const char *src); + +extern int OpenLogF(HANDLE file); +extern int WriteLog(HANDLE file, const char* data, int size, int forceFlush); +extern void DailyReopenLogF(HANDLE file); +extern unsigned int HashString(const char *name, unsigned int hash, + int endOnQuery, int skipLastIfDot); + +#define FlushLogF(h) WriteLog(h, NULL, 0, TRUE) + +#define MASK 0xFFFFFFFF +#define _rotl(Val, Bits) ((((Val)<<(Bits)) | (((Val) & MASK)>>(32 - (Bits)))) & MASK) /* nice exit support */ -void NiceExitBack(int val, char *reason, char *file, int line); +extern void NiceExitBack(int val, char *reason, char *file, int line); #define NiceExit(val, reason) NiceExitBack(val, reason, __FILE__, __LINE__) diff --git a/debug.c b/debug.c new file mode 100644 index 0000000..6878994 --- /dev/null +++ b/debug.c @@ -0,0 +1,177 @@ +#include +#include "codemuxlib.h" +#include "debug.h" +#include "queue.h" + +#ifdef DEBUG_MEMORY_LEAK + +/* Maximum length of the location string containing function, file and + the line number of the memory allocation part in the original + source code. The location info is added in front of the pointer + when allocating memory and return p + MAX_LOCATION_STRLEN to the + user */ +#define MAX_LOCATION_STRLEN 512 + +typedef struct MemoryAllocInfo { + char *mi_locstr; /* location string "__FUNCTION__:__LINE__" */ + int mi_count; /* allocated memory counts */ + LIST_ENTRY(MemoryAllocInfo) mi_hash; + LIST_ENTRY(MemoryAllocInfo) mi_all; +} MemoryAllocInfo; + +#define MAX_BINS 257 /* a prime number near 256 */ +static LIST_HEAD(, MemoryAllocInfo) miBins[MAX_BINS]; +static LIST_HEAD(, MemoryAllocInfo) miHead = LIST_HEAD_INITIALIZER(miHead); + +/*-------------------------------------------------------------------------*/ +void +dbg_print_memtrace(void) +{ + MemoryAllocInfo *walk; + + TRACE("memory alloc counts dump begins\n"); + LIST_FOREACH(walk, &miHead, mi_all) { + TRACE("%-50s: %d\n", walk->mi_locstr, walk->mi_count); + } + TRACE("memory alloc counts dump ends\n"); +} +/*-------------------------------------------------------------------------*/ +static void +increase_alloc_count(char* p, const char* func, + const char* file, const int line) +{ + int bin; + MemoryAllocInfo* walk; + +#define MAX_LINE_DIGIT 7 /* million lines of code per file is way too much */ +#define LOCSTR_LENGH (strlen(func) + strlen(file) + MAX_LINE_DIGIT + 3) + + if (LOCSTR_LENGH >= MAX_LOCATION_STRLEN) { + TRACE("over the length limit %s:%d\n", func, line); + FlushLogF(hdebugLog); + exit(-1); + } + snprintf(p, MAX_LOCATION_STRLEN, "%s:%s:%d", func, file, line); + + bin = (int)(HashString(p, 0, FALSE, FALSE) % MAX_BINS); + LIST_FOREACH(walk, &miBins[bin], mi_hash) { + if (strcmp(walk->mi_locstr, p) == 0) { /* match */ + walk->mi_count++; + return; + } + } + + /* allocate it if not found */ + if ((walk = (MemoryAllocInfo *)calloc(1, sizeof(MemoryAllocInfo))) == NULL) { + TRACE("calloc failed\n"); + FlushLogF(hdebugLog); + exit(-1); + } + if ((walk->mi_locstr = strdup(p)) == NULL) { + TRACE("calloc failed\n"); + FlushLogF(hdebugLog); + exit(-1); + } + walk->mi_count++; + LIST_INSERT_HEAD(&miBins[bin], walk, mi_hash); + LIST_INSERT_HEAD(&miHead, walk, mi_all); +} +/*-------------------------------------------------------------------------*/ +static void +decrease_alloc_count(char *p, const char* func, + const char* file, const int line) +{ + int bin = (int)(HashString(p, 0, FALSE, FALSE) % MAX_BINS); + MemoryAllocInfo* walk; + + LIST_FOREACH(walk, &miBins[bin], mi_hash) { + if (strcmp(walk->mi_locstr, p) == 0) { /* match */ + walk->mi_count--; + if (walk->mi_count == 0) { + LIST_REMOVE(walk, mi_hash); + LIST_REMOVE(walk, mi_all); + free(walk->mi_locstr); + free(walk); + } + return; + } + } + + TRACE("decrease failed %s:%s:%d\n", func, file, line); + FlushLogF(hdebugLog); + exit(-1); +} +/*-------------------------------------------------------------------------*/ +void * +dbgcalloc(size_t nmemb, size_t size, + const char* func, const char* file, const int line) +{ + int msize = nmemb * size + MAX_LOCATION_STRLEN; + char *p; + + if ((p = (char *)calloc(1, msize)) != NULL) { + increase_alloc_count(p, func, file, line); + return (void *)(p + MAX_LOCATION_STRLEN); + } + return NULL; +} +/*-------------------------------------------------------------------------*/ +void * +dbgmalloc(size_t size, const char* func, const char* file, const int line) +{ + int msize = size + MAX_LOCATION_STRLEN; + char *p; + + if ((p = (char *)malloc(msize)) != NULL) { + increase_alloc_count(p, func, file, line); + return (void *)(p + MAX_LOCATION_STRLEN); + } + return NULL; +} +/*-------------------------------------------------------------------------*/ +void * +dbgrealloc(void *ptr, size_t size, + const char* func, const char* file, const int line) +{ + int msize = size + MAX_LOCATION_STRLEN; + char *p; + + if (ptr != NULL) { + ptr -= MAX_LOCATION_STRLEN; + decrease_alloc_count(ptr, func, file, line); + } + + if ((p = (char *)realloc(ptr, msize)) != NULL) { + increase_alloc_count(p, func, file, line); + return (void *)(p + MAX_LOCATION_STRLEN); + } + return NULL; +} +/*-------------------------------------------------------------------------*/ +char * +dbgstrdup(const char *s, const char* func, const char* file, const int line) +{ + int msize = strlen(s) + 1 + MAX_LOCATION_STRLEN; + char *p; + + if ((p = (char *)malloc(msize))) { + increase_alloc_count(p, func, file, line); + p += MAX_LOCATION_STRLEN; + strcpy(p, s); + return p; + } + return NULL; +} +/*-------------------------------------------------------------------------*/ +void +dbgfree(void *ptr, const char* func, const char* file, const int line) +{ + /* should free the original pointer */ + char* chptr = (char *)ptr; + + chptr -= MAX_LOCATION_STRLEN; + decrease_alloc_count(chptr, func, file, line); + free(chptr); +} +#endif + diff --git a/debug.h b/debug.h index 566885c..bb46c12 100644 --- a/debug.h +++ b/debug.h @@ -10,19 +10,19 @@ TRACE1 : print "buf" whose size is "size" */ -#define DEBUG - -// extern HANDLE hdebugLog; -// extern int defaultTraceSync; -#define TRACE0(fmt, msg...) { \ - char __buf[2048]; \ - if (hdebugLog) { \ - snprintf(__buf, sizeof(__buf), fmt, ##msg); \ - WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync); \ - } \ +//#define DEBUG +#ifdef DEBUG +extern HANDLE hdebugLog; +extern int defaultTraceSync; +#define TRACE0(fmt, msg...) { \ + char __buf[2048]; \ + if (hdebugLog) { \ + snprintf(__buf, sizeof(__buf), fmt, ##msg); \ + WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync); \ + } \ } -#define TRACE1(buf, size) { \ - WriteLog(hdebugLog, buf, size, defaultTraceSync); \ +#define TRACE1(buf, size) { \ + WriteLog(hdebugLog, buf, size, defaultTraceSync); \ } #define TRACE(fmt, msg...) { \ char __buf[2048]; \ @@ -38,20 +38,11 @@ WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync); \ } \ } - -#ifndef HERE -#define HERE TRACE("file %s, line %d, func %s\n", __FILE__, __LINE__, __FUNCTION__) -#endif - -#ifdef DEBUG -#define ASSERT(exp) { \ - if (!(exp)) { \ - TRACE("ASSERTION (%s) FAILED in %s (%s:%d)\n", \ - (#exp), __FUNCTION__, __FILE__, __LINE__); \ - } \ -} #else -#define ASSERT(exp) 1 ? (void)0 : (exp) +#define TRACE0(fmt, msg...) (void)0 +#define TRACE1(fmt, msg...) (void)0 +#define TRACE(fmt, msg...) (void)0 +#define TRACEX(fmt) (void)0 #endif // DEBUG /*-------------------------------------------------------------- @@ -71,11 +62,15 @@ #else +#ifndef DEBUG +#error "define DEBUG first to make DEBUG_MEMORY_LEAK work" +#endif + #define xcalloc(nmemb, size) dbgcalloc(nmemb, size, __FUNCTION__, \ __FILE__, __LINE__) -#define xmalloc(size) dbgmalloc(size, __FUNCTION__,\ +#define xmalloc(size) dbgmalloc(size, __FUNCTION__, \ __FILE__, __LINE__) -#define xrealloc(ptr, size) dbgrealloc(ptr, size, __FUNCTION__,\ +#define xrealloc(ptr, size) dbgrealloc(ptr, size, __FUNCTION__, \ __FILE__, __LINE__) #define xstrdup(s) dbgstrdup(s, __FUNCTION__, __FILE__, __LINE__) #define xfree(ptr) dbgfree(ptr, __FUNCTION__, __FILE__, __LINE__) diff --git a/queue.h b/queue.h new file mode 100644 index 0000000..98a61f2 --- /dev/null +++ b/queue.h @@ -0,0 +1,562 @@ +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. 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. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $ + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +#if 0 +we do not seem to have this on linux +#include /* for __offsetof */ +#endif + +/* + * This file defines five types of data structures: singly-linked lists, + * singly-linked tail queues, lists, tail queues, and circular queues. + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A singly-linked tail queue is headed by a pair of pointers, one to the + * head of the list and the other to the tail of the list. The elements are + * singly linked for minimum space and pointer manipulation overhead at the + * expense of O(n) removal for arbitrary elements. New elements can be added + * to the list after an existing element, at the head of the list, or at the + * end of the list. Elements being removed from the head of the tail queue + * should use the explicit macro for this purpose for optimum efficiency. + * A singly-linked tail queue may only be traversed in the forward direction. + * Singly-linked tail queues are ideal for applications with large datasets + * and few or no removals or for implementing a FIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + * + * + * SLIST LIST STAILQ TAILQ CIRCLEQ + * _HEAD + + + + + + * _HEAD_INITIALIZER + + + + + + * _ENTRY + + + + + + * _INIT + + + + + + * _EMPTY + + + + + + * _FIRST + + + + + + * _NEXT + + + + + + * _PREV - - - + + + * _LAST - - + + + + * _FOREACH + + + + + + * _FOREACH_REVERSE - - - + + + * _INSERT_HEAD + + + + + + * _INSERT_BEFORE - + - + + + * _INSERT_AFTER + + + + + + * _INSERT_TAIL - - + + + + * _REMOVE_HEAD + - + - - + * _REMOVE + + + + + + * + */ + +/* + * Singly-linked List declarations. + */ +#define SLIST_HEAD(name, type) \ +struct name { \ + struct type *slh_first; /* first element */ \ +} + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ +struct { \ + struct type *sle_next; /* next element */ \ +} + +/* + * Singly-linked List functions. + */ +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) + +#define SLIST_FIRST(head) ((head)->slh_first) + +#define SLIST_FOREACH(var, head, field) \ + for ((var) = SLIST_FIRST((head)); \ + (var); \ + (var) = SLIST_NEXT((var), field)) + +#define SLIST_INIT(head) do { \ + SLIST_FIRST((head)) = NULL; \ +} while (0) + +#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ + SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ + SLIST_NEXT((slistelm), field) = (elm); \ +} while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) do { \ + SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ + SLIST_FIRST((head)) = (elm); \ +} while (0) + +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_REMOVE(head, elm, type, field) do { \ + if (SLIST_FIRST((head)) == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } \ + else { \ + struct type *curelm = SLIST_FIRST((head)); \ + while (SLIST_NEXT(curelm, field) != (elm)) \ + curelm = SLIST_NEXT(curelm, field); \ + SLIST_NEXT(curelm, field) = \ + SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ + } \ +} while (0) + +#define SLIST_REMOVE_HEAD(head, field) do { \ + SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ +} while (0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ +struct name { \ + struct type *stqh_first;/* first element */ \ + struct type **stqh_last;/* addr of last next element */ \ +} + +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ +struct { \ + struct type *stqe_next; /* next element */ \ +} + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) + +#define STAILQ_FIRST(head) ((head)->stqh_first) + +#define STAILQ_FOREACH(var, head, field) \ + for((var) = STAILQ_FIRST((head)); \ + (var); \ + (var) = STAILQ_NEXT((var), field)) + +#define STAILQ_INIT(head) do { \ + STAILQ_FIRST((head)) = NULL; \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_NEXT((tqelm), field) = (elm); \ +} while (0) + +#define STAILQ_INSERT_HEAD(head, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_FIRST((head)) = (elm); \ +} while (0) + +#define STAILQ_INSERT_TAIL(head, elm, field) do { \ + STAILQ_NEXT((elm), field) = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ +} while (0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY(head) ? \ + NULL : \ + ((struct type *) \ + ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) + +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) + +#define STAILQ_REMOVE(head, elm, type, field) do { \ + if (STAILQ_FIRST((head)) == (elm)) { \ + STAILQ_REMOVE_HEAD(head, field); \ + } \ + else { \ + struct type *curelm = STAILQ_FIRST((head)); \ + while (STAILQ_NEXT(curelm, field) != (elm)) \ + curelm = STAILQ_NEXT(curelm, field); \ + if ((STAILQ_NEXT(curelm, field) = \ + STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ + (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ + } \ +} while (0) + +#define STAILQ_REMOVE_HEAD(head, field) do { \ + if ((STAILQ_FIRST((head)) = \ + STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ + if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +/* + * List declarations. + */ +#define LIST_HEAD(name, type) \ +struct name { \ + struct type *lh_first; /* first element */ \ +} + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ +struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ +} + +/* + * List functions. + */ + +#define LIST_EMPTY(head) ((head)->lh_first == NULL) + +#define LIST_FIRST(head) ((head)->lh_first) + +#define LIST_FOREACH(var, head, field) \ + for ((var) = LIST_FIRST((head)); \ + (var); \ + (var) = LIST_NEXT((var), field)) + +#define LIST_INIT(head) do { \ + LIST_FIRST((head)) = NULL; \ +} while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ + LIST_NEXT((listelm), field)->field.le_prev = \ + &LIST_NEXT((elm), field); \ + LIST_NEXT((listelm), field) = (elm); \ + (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ +} while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + LIST_NEXT((elm), field) = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ +} while (0) + +#define LIST_INSERT_HEAD(head, elm, field) do { \ + if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ + LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ + LIST_FIRST((head)) = (elm); \ + (elm)->field.le_prev = &LIST_FIRST((head)); \ +} while (0) + +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_REMOVE(elm, field) do { \ + if (LIST_NEXT((elm), field) != NULL) \ + LIST_NEXT((elm), field)->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = LIST_NEXT((elm), field); \ +} while (0) + +/* + * Tail queue declarations. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * Tail queue functions. + */ +#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) + +#define TAILQ_FIRST(head) ((head)->tqh_first) + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = TAILQ_FIRST((head)); \ + (var); \ + (var) = TAILQ_NEXT((var), field)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_INIT(head) do { \ + TAILQ_FIRST((head)) = NULL; \ + (head)->tqh_last = &TAILQ_FIRST((head)); \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + TAILQ_NEXT((listelm), field) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + TAILQ_NEXT((elm), field) = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ + TAILQ_FIRST((head))->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + TAILQ_FIRST((head)) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + TAILQ_NEXT((elm), field) = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ +} while (0) + +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) + +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) + +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if ((TAILQ_NEXT((elm), field)) != NULL) \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ +} while (0) + +/* + * Circular queue declarations. + */ +#define CIRCLEQ_HEAD(name, type) \ +struct name { \ + struct type *cqh_first; /* first element */ \ + struct type *cqh_last; /* last element */ \ +} + +#define CIRCLEQ_HEAD_INITIALIZER(head) \ + { (void *)&(head), (void *)&(head) } + +#define CIRCLEQ_ENTRY(type) \ +struct { \ + struct type *cqe_next; /* next element */ \ + struct type *cqe_prev; /* previous element */ \ +} + +/* + * Circular queue functions. + */ +#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) + +#define CIRCLEQ_FIRST(head) ((head)->cqh_first) + +#define CIRCLEQ_FOREACH(var, head, field) \ + for ((var) = CIRCLEQ_FIRST((head)); \ + (var) != (void *)(head) || ((var) = NULL); \ + (var) = CIRCLEQ_NEXT((var), field)) + +#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ + for ((var) = CIRCLEQ_LAST((head)); \ + (var) != (void *)(head) || ((var) = NULL); \ + (var) = CIRCLEQ_PREV((var), field)) + +#define CIRCLEQ_INIT(head) do { \ + CIRCLEQ_FIRST((head)) = (void *)(head); \ + CIRCLEQ_LAST((head)) = (void *)(head); \ +} while (0) + +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \ + CIRCLEQ_PREV((elm), field) = (listelm); \ + if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \ + CIRCLEQ_LAST((head)) = (elm); \ + else \ + CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\ + CIRCLEQ_NEXT((listelm), field) = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ + CIRCLEQ_NEXT((elm), field) = (listelm); \ + CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \ + if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \ + CIRCLEQ_FIRST((head)) = (elm); \ + else \ + CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\ + CIRCLEQ_PREV((listelm), field) = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ + CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \ + CIRCLEQ_PREV((elm), field) = (void *)(head); \ + if (CIRCLEQ_LAST((head)) == (void *)(head)) \ + CIRCLEQ_LAST((head)) = (elm); \ + else \ + CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \ + CIRCLEQ_FIRST((head)) = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ + CIRCLEQ_NEXT((elm), field) = (void *)(head); \ + CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \ + if (CIRCLEQ_FIRST((head)) == (void *)(head)) \ + CIRCLEQ_FIRST((head)) = (elm); \ + else \ + CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \ + CIRCLEQ_LAST((head)) = (elm); \ +} while (0) + +#define CIRCLEQ_LAST(head) ((head)->cqh_last) + +#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) + +#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) + +#define CIRCLEQ_REMOVE(head, elm, field) do { \ + if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \ + CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \ + else \ + CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \ + CIRCLEQ_PREV((elm), field); \ + if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \ + CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \ + else \ + CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \ + CIRCLEQ_NEXT((elm), field); \ +} while (0) + +#ifdef _KERNEL + +/* + * XXX insque() and remque() are an old way of handling certain queues. + * They bogusly assumes that all queue heads look alike. + */ + +struct quehead { + struct quehead *qh_link; + struct quehead *qh_rlink; +}; + +#ifdef __GNUC__ + +static __inline void +insque(void *a, void *b) +{ + struct quehead *element = (struct quehead *)a, + *head = (struct quehead *)b; + + element->qh_link = head->qh_link; + element->qh_rlink = head; + head->qh_link = element; + element->qh_link->qh_rlink = element; +} + +static __inline void +remque(void *a) +{ + struct quehead *element = (struct quehead *)a; + + element->qh_link->qh_rlink = element->qh_rlink; + element->qh_rlink->qh_link = element->qh_link; + element->qh_rlink = 0; +} + +#else /* !__GNUC__ */ + +void insque __P((void *a, void *b)); +void remque __P((void *a)); + +#endif /* __GNUC__ */ + +#endif /* _KERNEL */ + +#endif /* !_SYS_QUEUE_H_ */ -- 2.43.0