diff options
| -rw-r--r-- | lib/Makefile.am | 6 | ||||
| -rw-r--r-- | lib/heap.c | 504 | ||||
| -rw-r--r-- | lib/heap.h | 96 | ||||
| -rw-r--r-- | lib/memtypes.c | 10 | ||||
| -rw-r--r-- | lib/plist.c | 87 | ||||
| -rw-r--r-- | lib/qpthreads.c | 435 | ||||
| -rw-r--r-- | lib/qpthreads.h | 393 | ||||
| -rw-r--r-- | lib/qtime.c | 128 | ||||
| -rw-r--r-- | lib/qtime.h | 213 | ||||
| -rw-r--r-- | lib/zassert.h | 38 |
10 files changed, 1855 insertions, 55 deletions
diff --git a/lib/Makefile.am b/lib/Makefile.am index f655ac39..08f834ae 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -12,7 +12,8 @@ libzebra_la_SOURCES = \ sockunion.c prefix.c thread.c if.c memory.c buffer.c table.c hash.c \ filter.c routemap.c distribute.c stream.c str.c log.c plist.c \ zclient.c sockopt.c smux.c md5.c if_rmap.c keychain.c privs.c \ - sigevent.c pqueue.c jhash.c memtypes.c workqueue.c symtab.c + sigevent.c pqueue.c jhash.c memtypes.c workqueue.c symtab.c heap.c \ + qtime.c qpthreads.c BUILT_SOURCES = memtypes.h route_types.h @@ -27,7 +28,8 @@ pkginclude_HEADERS = \ str.h stream.h table.h thread.h vector.h version.h vty.h zebra.h \ plist.h zclient.h sockopt.h smux.h md5.h if_rmap.h keychain.h \ privs.h sigevent.h pqueue.h jhash.h zassert.h memtypes.h \ - workqueue.h route_types.h symtab.h + workqueue.h route_types.h symtab.h heap.h \ + qtime.h qpthreads.h EXTRA_DIST = regex.c regex-gnu.h memtypes.awk route_types.awk route_types.txt diff --git a/lib/heap.c b/lib/heap.c new file mode 100644 index 00000000..63e3fe75 --- /dev/null +++ b/lib/heap.c @@ -0,0 +1,504 @@ +/* Generic heap data structure -- functions. + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include <zebra.h> + +#include "heap.h" +#include "memory.h" + +/* Heaps are implemented as a structure which includes a vector structure. + * So items in the heap are items in a vector, which are pointers to the item + * values. + * + * The heap structure may be statically allocated, embedded in another + * structure, or allocated dynamically. In any case the heap operations + * require the address of the heap structure -- see typedef for heap. + * + * An essential component of a heap is its comparison function. So, cannot + * use a heap before it has been initialised and the comparison function set. + * (This is unlike a vector, which may be implicitly initialised empty by + * zeroizing the vector structure.) + * + * Items may be pushed onto or popped off the heap, which is organised so that + * the top item has the smallest value -- according to the heap's comparison + * function. (For equal values, the order is undefined.) + * + * The top item in the heap may be examined, and its value may be updated. + * (Updating the top item is more efficient than popping and then pushing it.) + * + * Items may be deleted from the heap. Items may have their value updated + * while they are in the heap. Both of these operations cause the heap to be + * reorganised to maintain the heap's partial ordering. Note: these operations + * require knowledge of where in the heap the item is -- which, by default, is + * done by a linear scan of the heap. For large heaps, there is the option to + * keep a "backlink" from the item to it's heap position. + * + * Vectors may be pushed onto a heap -- copying or moving the contents. + * + * Heaps may popped to a vector -- copying or moving the contents. The + * resulting vector is fully sorted. + * + * ---------------------------- + * Comparison function for heap. + * + * int heap_cmp(...** a, ...**) ... + * + * Must return -1, 0, +1 : where -1 => a < b, 0 => a == b & +1 => a > b + * + * Heap will sort "smallest" to the top. If you want the biggest at the top, + * return -1 * usual comparison. Note that the effective heap ordering for + * equal values is, essentially, random. + * + * NB: like other comparison functions (cf qsort) the parameters are pointers + * to pointers to the value. + * + * NB: there should never be NULL items in the heap. + */ + +/* Forward reference the mechanics. */ +static void heap_bubble(heap h, vector_index i, p_vector_item p_v) ; +static void heap_bubble_up(heap h, vector_index i, p_vector_item p_v); +static void heap_bubble_down(heap h, vector_index i, p_vector_item p_v) ; + +/*============================================================================== + * Initialisation, allocation, reset etc. + */ + +static heap +heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp, + int with_backlink, unsigned int backlink_offset) +{ + assert(cmp != NULL) ; /* or there will be tears */ + + h->cmp = cmp ; + h->state = with_backlink ? Heap_Has_Backlink : 0 ; + h->backlink_offset = backlink_offset ; + + if (new_vector) + vector_init_new(&h->v, size) ; + else + vector_re_init(&h->v, size) ; + + return h ; +} ; + +/* Initialize heap. + * + * Allocates heap structure if none given. + * Does not allocate the underlying vector if the heap is initialised empty. + * + * eg: + * + * ... = heap_new_init_simple(NULL, 0, (heap_cmp*)my_cmp) + * + * NB: when initialising an existing heap structure it is ESSENTIAL that + * any previous heap and its contents have been released, because this + * function simply discards whatever was there before. (This function may + * be called to initialise a heap structure which has never been + * initialised.) + * + * Backlink: + * + * The heap_delete_item and heap_update_item functions need the heap + * position of the item. The default way of finding that is to scan the + * underlying heap array, looking for the address of the item. + * + * If either of these functions is done often and on large heaps, it is + * possible to speed this up by implementing a 'backlink'. This requires + * a field of type heap_backlink_t in the item structure, and it is the + * offset of that which must be initialised here, eg: + * + * ... = heap_new_init_backlink(NULL, 0, (heap_cmp*)my_cmp, + * offset_of(struct xxx_heap_item, backlink)) ; + * + * This adds a little extra work to every change in the heap -- keeping the + * backlink of any moved item up to date. But avoids a linear search for + * every heap_delete_item or heap_update_item. + */ +heap +heap_init_new(heap h, vector_index size, heap_cmp* cmp, + int with_backlink, unsigned int backlink_offset) +{ + if (h == NULL) + h = XCALLOC(MTYPE_HEAP, sizeof(struct heap)) ; + else + memset(h, 0, sizeof(struct heap)) ; + + return heap_setup(h, 1, size, cmp, with_backlink, backlink_offset) ; +} ; + +/* Re-Initialize heap (or create a new one, if h == NULL). + * + * Allocates heap structure if none given -- allocating vector if size != 0. + * Otherwise, re-initialise the heap and any vector (reusing its memory). + * + * NB: when re-initialising an existing heap it is the caller's + * responsibility to release any item values *before* doing this. + */ +heap +heap_re_init(heap h, vector_index size, heap_cmp* cmp, + int with_backlink, unsigned int backlink_offset) +{ + if (h == NULL) + return heap_init_new(h, size, cmp, with_backlink, backlink_offset) ; + else + return heap_setup(h, 0, size, cmp, with_backlink, backlink_offset) ; +} ; + +/* Release heap contents (underlying vector), and (if required) release the + * heap structure. + * + * Return NULL if releases heap, otherwise the address of the heap. + * + * If does not release the heap, it retains the comparison function and any + * backlink setting -- so heap can be reused without reinitialising it. + * + * NB: it is the callers responsibility to release any heap item values + * *before* doing this. + */ +heap +heap_reset(heap h, int free_structure) +{ + vector_reset(&h->v, 0) ; + + if (free_structure) + { + XFREE(MTYPE_VECTOR, h) ; + return NULL ; + } ; + + return h ; +} ; + +/* Remove last item from heap. + * + * If heap is empty, release the underlying vector, and (if required) release + * the heap structure. + * + * Useful for emptying out and discarding a heap: + * + * while ((p_v = heap_ream_out(v, 1))) + * ... do what's required to release the item p_v + * + * Returns NULL when heap is empty. + * + * If does not release the heap, it retains the comparison function and any + * backlink setting -- so heap can be reused without reinitialising it. + * + * NB: by 'last' this does NOT mean last according to the heap ordering, + * it just means last in the underlying vector -- which won't be the + * first in heap order (unless heap contains only one item). + */ +p_vector_item +heap_ream(heap h, int free_structure) +{ + p_vector_item p_v ; + + if (h == NULL) + return NULL ; + + if ((p_v = vector_ream_keep(&h->v)) == NULL) + heap_reset(h, free_structure) ; + + return p_v ; +} ; + +/*============================================================================== + * Simple Heap Operations + */ + +/* Push given item onto the heap */ +void +heap_push_item(heap h, p_vector_item p_v) +{ + assert(p_v) ; /* no NULLs, thank you. */ + heap_bubble_up(h, vector_extend_by_1(&h->v), p_v) ; +} ; + +/* Pop item off the heap. + * + * Returns NULL if heap is empty. + */ +p_vector_item +heap_pop_item(heap h) +{ + p_vector_item p_v ; + p_vector_item p_x ; + + p_x = vector_pop_item(&h->v) ; /* extract last item, if any */ + if (h->v.end == 0) + return p_x ; /* done if last was also first */ + + p_v = h->v.p_items[0] ; /* this is what we are popping */ + + heap_bubble_down(h, 0, p_x) ; /* reposition what was the last item */ + /* updating any backlink */ + return p_v ; +} ; + +/* Get address of top item on heap. Re-establish heap order if required. + * + * Returns NULL if heap is empty. + */ +p_vector_item +heap_top_item(heap h) +{ + return vector_get_first_item(&h->v) ; /* if any */ +} ; + +/* Update heap to reflect new value of top item. */ +void +heap_update_top_item(heap h) +{ + heap_bubble_down(h, 0, vector_get_first_item(&h->v)) ; +} ; + +/*============================================================================== + * Heap Operations which use 'backlink', if implemented. + */ + +static vector_index heap_find_item(heap h, p_vector_item) ; + +/* Delete given item from the heap. + * + * See notes on backlink, above. + * + * NB: do NOT try this on items which are not in the given heap ! + */ +void +heap_delete_item(heap h, p_vector_item p_v) +{ + p_vector_item p_x ; + vector_index i ; + + i = heap_find_item(h, p_v) ; + + p_x = vector_pop_item(&h->v) ; /* extract last item, if any */ + + if (i == h->v.end) + return ; /* stop now if deleting last item */ + + heap_bubble(h, i, p_x) ; /* move what was last into position */ + /* updating any backlink */ +} ; + +/* Update heap to reflect new value of given item. + * + * See notes on backlink, above. + */ +void heap_update_item(heap h, p_vector_item p_v) +{ + heap_bubble(h, heap_find_item(h, p_v), p_v) ; +} ; + +/*============================================================================== + * Other Heap Operations. + */ + +/* Push entire vector onto heap copying or moving items as required. + * + * Copy or move vector to end of heap's vector, then move each + * (non-NULL) item into heap order. + */ +void +heap_push_vector(heap h, vector v, int move_vector) +{ + vector_index i = h->v.end ; + vector_index e ; + vector_index n = v->end ; + + if (move_vector) + vector_move_append(&h->v, v) ; + else + vector_copy_append(&h->v, v) ; + + e = i ; /* old end of the heap. */ + while (n--) { + p_vector_item p_v = h->v.p_items[i++] ; + if (p_v != NULL) + heap_bubble_up(h, e++, p_v) ; /* move new item into position in heap */ + /* setting any backlink */ + } ; + + h->v.end = e ; /* new end of heap */ +} ; + +/* Pop given heap to vector -- creating vector if required (v == NULL). + * + * Resulting vector is fully sorted. + * + * Moves or copies the contents of the heap. + * + * NB: when creating new vector, will be exactly the required size. + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to release any existing items if that is required. + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to ensure the vector structure is currently valid. +*/ + +vector +heap_pop_vector(vector v, heap h, int move_heap) +{ + vector_index n = h->v.end ; + vector_index i ; + + v = vector_re_init(v, n) ; + v->end = n ; + + for (i = 0 ; i < n ; i++) + v->p_items[i] = heap_pop_item(h) ; + + if (!move_heap) + vector_copy_here(&h->v, v) ; /* fully sorted is also heap ordered ! */ + + return v ; +} ; + +/*============================================================================== + * The Heap internal mechanics. + */ + +/* Returns pointer to backlink value in heap item: lvalue or rvalue */ +#define HEAP_BACKLINK(h, p_v) \ + *(heap_backlink_t*)((char*)(p_v) + (h)->backlink_offset) +/* Sets backlink, if required. */ +#define heap_set_backlink(h, p_v, i) \ + if ((h)->state & Heap_Has_Backlink) HEAP_BACKLINK(h, p_v) = (i) + +/* Returns index of parent. */ +#define HEAP_UP(i) (((i) * 2) + 1) +/* Returns index of left child. */ +#define HEAP_DOWN(i) (((i) - 1) / 2) + +/* Insert given item in the required place in heap, given that there is now + * a hole at the given position -- may move up or down the heap, or stay put. + * + * Bubbles up or down as required. + * + * Note that this sets the backlink on the given item. + */ +static void +heap_bubble(heap h, vector_index i, p_vector_item p_v) +{ + /* If this is < parent, we bubble upwards. */ + if ((i != 0) && (h->cmp(&p_v, &h->v.p_items[HEAP_UP(i)]) < 0)) + heap_bubble_up(h, i, p_v) ; + /* Otherwise we try bubbling downwards. */ + else + heap_bubble_down(h, i, p_v) ; +} ; + +/* Insert given item in the required place in heap, given that there is now + * a hole at the given position -- where we know may *only* move up the heap. + * + * Note that this sets the backlink on the given item. + * + * NB: ignores anything in the heap beyond 'i' -- in particular does not use + * v.end at all. So this can be used to work along a vector and bring + * items into heap order. + */ +static void +heap_bubble_up(heap h, vector_index i, p_vector_item p_v) +{ + p_vector_item* ha = h->v.p_items ; /* underlying array */ + + while (i != 0) + { + vector_index ip = HEAP_UP(i) ; + p_vector_item p_p = &ha[ip] ; + + if (h->cmp(&p_p, &p_v) <= 0) + break ; /* stop when parent is <= us */ + ha[i] = p_p ; /* move parent down... */ + heap_set_backlink(h, p_p, i) ; /* ...updating any backlink */ + i = ip ; /* move up the heap */ + } + + ha[i] = p_v ; /* place in new position... */ + heap_set_backlink(h, p_v, i) ; /* ...updating any backlink */ +} ; + +/* Insert given item in the required place in heap, given that there is now + * a hole at the given position -- where we know may *only* move down the heap. + * + * Note that this sets the backlink on the given item. + */ +static void +heap_bubble_down(heap h, vector_index i, p_vector_item p_v) +{ + vector_index e = h->v.end ; /* end of heap */ + p_vector_item* ha = h->v.p_items ; /* underlying array */ + + while (1) + { + vector_index ic ; /* index of child */ + vector_index is ; /* index of sibling */ + p_vector_item p_c ; /* pointer to child */ + p_vector_item p_s ; /* pointer to sibling */ + + ic = HEAP_DOWN(i) ; + if (ic >= e) + break ; /* Quit if run out of heap ! */ + p_c = &ha[ic] ; + + is = ic + 1 ; + if (is < e) + { + p_s = &ha[is] ; + if (h->cmp(&p_s, &p_c) < 0) + { + ic = is ; /* select smaller sibling */ + p_c = p_s ; + } + } + + if (h->cmp(&p_v, &p_c) <= 0) + break ; /* stop when we are <= both children */ + ha[i] = p_c ; /* move smaller child up */ + heap_set_backlink(h, p_c, i) ; /* ...updating any backlink */ + i = ic ; /* move down the heap */ + } + + ha[i] = p_v ; + heap_set_backlink(h, p_v, i) ; +} ; + +/* Find index of given item in the given heap. */ +static vector_index +heap_find_item(heap h, p_vector_item p_v) +{ + vector_index i ; + + if (h->state & Heap_Has_Backlink) + i = HEAP_BACKLINK(h, p_v) ; + else + { + for (i = 0 ; i < h->v.end ; ++i) + if (h->v.p_items[i] == p_v) + break ; + } ; + + assert((i < h->v.end) && (h->v.p_items[i] == p_v)) ; + + return i ; +} ; diff --git a/lib/heap.h b/lib/heap.h new file mode 100644 index 00000000..d91fff4a --- /dev/null +++ b/lib/heap.h @@ -0,0 +1,96 @@ +/* Generic heap data structure -- header. + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + *. + * This file is part of GNU Zebra. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#ifndef _ZEBRA_HEAP_H +#define _ZEBRA_HEAP_H + +#include "vector.h" + +/* Macro in case there are particular compiler issues. */ +#ifndef Inline + #define Inline static inline +#endif + +typedef int heap_cmp(p_vector_item* a, p_vector_item*) ; + +enum heap_state { + Heap_Has_Backlink = 0x01, /* Set if backlink set */ +}; + +struct heap +{ + heap_cmp* cmp ; + + enum heap_state state ; + unsigned int backlink_offset ; + + struct vector v ; +}; + +typedef struct heap* heap; + +typedef vector_index heap_backlink_t ; + +/* Prototypes. */ + +extern heap heap_init_new(heap h, vector_index size, heap_cmp* cmp, + int with_backlink, unsigned int backlink_offset) ; +#define heap_init_new_simple(h, size, cmp) \ + heap_init_new(h, size, cmp, 0, 0) +#define heap_init_new_backlinked(h, size, cmp, off) \ + heap_init_new(h, size, cmp, 1, off) + +extern heap heap_re_init(heap h, vector_index size, heap_cmp* cmp, + int with_backlink, unsigned int backlink_offset) ; +#define heap_re_init_simple(h, size, cmp) \ + heap_re_init(h, size, cmp, 0, 0) +#define heap_re_init_backlinked(h, size, cmp, off) \ + heap_re_init(h, size, cmp, 1, off) + +extern heap heap_reset(heap h, int free_structure) ; +extern p_vector_item heap_ream(heap h, int free_structure) ; + +/* Reset heap and free the heap structure. */ +#define heap_reset_free(h) heap_reset(h, 1) ; +/* Reset heap but keep the heap structure. */ +#define heap_reset_keep(h) heap_reset(h, 0) ; +/* Ream out heap and free the heap structure. */ +#define heap_ream_free(h) heap_ream_out(h, 1) ; +/* Ream out heap but keep the heap structure. */ +#define heap_ream_keep(h) heap_ream_out(h, 0) ; + +extern void heap_push_item(heap h, p_vector_item p_v) ; +extern p_vector_item heap_pop_item(heap h) ; +extern p_vector_item heap_top_item(heap h) ; +extern void heap_update_top_item(heap h) ; + +extern void heap_delete_item(heap h, p_vector_item p_v) ; +extern void heap_update_item(heap h, p_vector_item p_v) ; + +extern void heap_push_vector(heap h, vector v, int move_vector) ; +#define heap_push_vector_copy(h, v) \ + heap_push_vector(h, v, 0) +#define heap_push_vector_move(h, v) \ + heap_push_vector(h, v, 1) +extern vector heap_pop_vector(vector v, heap h, int move_heap) ; +#define heap_pop_vector_copy(v, h) \ + heap_pop_vector(v, h, 0) +#define heap_pop_vector_move(v, h) \ + heap_pop_vector(v, h, 1) + +extern vector heap_vector(heap h, int unset_heap_order) ; + +#endif /* _ZEBRA_HEAP_H */ diff --git a/lib/memtypes.c b/lib/memtypes.c index 197fb88c..fb2557c8 100644 --- a/lib/memtypes.c +++ b/lib/memtypes.c @@ -16,18 +16,22 @@ struct memory_list memory_list_lib[] = { { MTYPE_TMP, "Temporary memory" }, { MTYPE_STRVEC, "String vector" }, - { MTYPE_VECTOR, "Vector structure" }, - { MTYPE_VECTOR_BODY, "Vector body" }, + { MTYPE_VECTOR, "Vector structure" }, + { MTYPE_VECTOR_BODY, "Vector body" }, { MTYPE_SYMBOL_TABLE, "Symbol Table structure" }, { MTYPE_SYMBOL_BASES, "Symbol Table chain bases" }, { MTYPE_SYMBOL, "Symbol" }, { MTYPE_SYMBOL_REF, "Symbol Reference" }, + { MTYPE_HEAP, "Heap structure" }, { MTYPE_LINK_LIST, "Link List" }, { MTYPE_LINK_NODE, "Link Node" }, { MTYPE_THREAD, "Thread" }, { MTYPE_THREAD_MASTER, "Thread master" }, { MTYPE_THREAD_STATS, "Thread stats" }, - { MTYPE_THREAD_FUNCNAME, "Thread function name" }, + { MTYPE_THREAD_FUNCNAME, "Thread function name" }, + { MTYPE_QPT_THREAD_ATTR, "qpt thread attributes" }, + { MTYPE_QPT_MUTEX, "qpt mutex" }, + { MTYPE_QPT_COND, "qpt condition variable" }, { MTYPE_VTY, "VTY" }, { MTYPE_VTY_OUT_BUF, "VTY output buffer" }, { MTYPE_VTY_HIST, "VTY history" }, diff --git a/lib/plist.c b/lib/plist.c index d222a6a8..b01c48f6 100644 --- a/lib/plist.c +++ b/lib/plist.c @@ -499,19 +499,6 @@ prefix_list_new(struct prefix_master* pm, struct symbol* sym, afi_t afi) return new ; } ; -/* Release given prefix_list -- assumes all contents of the prefix list have - * already been released... - * - * Unsets the symbol value and discards the prefix_list structure. - * Assumes that the contents of the prefix_list have already been emptied out. - */ -static void -prefix_list_free (struct prefix_list *plist) -{ - symbol_unset_value(plist->sym) ; - XFREE (MTYPE_PREFIX_LIST, plist) ; -} - /* Initialise prefix_list entry -- cleared to zeros. */ static struct prefix_list_entry * prefix_list_entry_init(struct prefix_list_entry * pe) @@ -541,6 +528,43 @@ prefix_dup_cache_free(struct prefix_master* pm) vector_reset(&pm->dup_cache, 0) ; } +/* Delete prefix_list from prefix_list_master and free it and its contents. */ +/* The prefix_list's symbol is set undefined. */ +static void +prefix_list_delete (struct prefix_list* plist) +{ + struct prefix_master* pm = plist->master ; + unsigned int i ; + struct prefix_list_entry* pe ; + + /* Free all the prefix_list_entries, then free the vector they live in. */ + for (VECTOR_ITEMS(&plist->list, pe, i)) + prefix_list_entry_free(pe) ; + vector_reset(&plist->list, 0) ; + + /* If there is a description, release that now. */ + if (plist->desc) + XFREE (MTYPE_TMP, plist->desc); + + /* Can no longer own the dup_cache. */ + if (pm->cache_owner == plist) + prefix_dup_cache_free(pm) ; + + /* Symbol no longer has a value & drop reference. */ + symbol_unset_value(plist->sym) ; + plist->sym = symbol_dec_ref(plist->sym) ; + + /* Finally, release the prefix_list structure. */ + XFREE (MTYPE_PREFIX_LIST, plist) ; + + /* No longer have a recently changed prefix-list */ + pm->recent = NULL ; + + /* Tell the world. */ + if (pm->delete_hook) + (*pm->delete_hook) (NULL); +} ; + /*============================================================================== * Operations on prefix_lists */ @@ -583,43 +607,6 @@ prefix_list_get (struct prefix_master* pm, const char *name, afi_t afi) return plist ? plist : prefix_list_new(pm, sym, afi) ; } ; -/* Delete prefix_list from prefix_list_master and free it and its contents. */ -/* The prefix_list's symbol is set undefined. */ -static void -prefix_list_delete (struct prefix_list* plist) -{ - struct prefix_master* pm = plist->master ; - unsigned int i ; - struct prefix_list_entry* pe ; - - /* Free all the prefix_list_entries, then free the vector they live in. */ - for (VECTOR_ITEMS(&plist->list, pe, i)) - prefix_list_entry_free(pe) ; - vector_reset(&plist->list, 0) ; - - /* If there is a description, release that now. */ - if (plist->desc) - XFREE (MTYPE_TMP, plist->desc); - - /* Can no longer own the dup_cache. */ - if (pm->cache_owner == plist) - prefix_dup_cache_free(pm) ; - - /* Symbol no longer has a value & drop reference. */ - symbol_unset_value(plist->sym) ; - plist->sym = symbol_dec_ref(plist->sym) ; - - /* Finally, release the prefix_list itself. */ - prefix_list_free(plist) ; - - /* No longer have a recently changed prefix-list */ - pm->recent = NULL ; - - /* Tell the world. */ - if (pm->delete_hook) - (*pm->delete_hook) (NULL); -} ; - /*============================================================================== * Operations on prefix_list_entry */ diff --git a/lib/qpthreads.c b/lib/qpthreads.c new file mode 100644 index 00000000..87ee00d3 --- /dev/null +++ b/lib/qpthreads.c @@ -0,0 +1,435 @@ +/* Quagga Pthreads support -- header + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#include "qpthreads.h" +#include "memory.h" + +/*============================================================================== + * Quagga Pthread Interface -- qpt_xxxx + * + * Here (and in qpthreads.h) are captured all the pthreads features used in + * Quagga. + * + * This provides: + * + * * "wrappers" around functions which should not fail, but whose return + * code it is best to check... at least in a debug environment. + * + * * the possibility of a separate no pthreads build where pthread facilities + * are either dummied out or otherwise dealt with. + * + * * the ability to add any work-arounds which may be required if poorly + * conforming pthreads implementations are encountered + * + * Pthread Thread Attributes -- Scheduling + * ======================================= + * + * Pthreads defines some useful looking real-time scheduling features. + * + * One would like to be able to give I/O intensive threads an advantage over + * CPU bound threads. + * + * Unfortunately, conformance allows a system to have its own scheduling + * system -- so long as the standard ones are implemented. Further, there is + * no way of telling what priority values are reasonable, even in the standard + * scheduling policies. + * + * The approach taken here is that by default a thread will be created with + * the system default attributes -- which may mean inheriting the creating + * thread's scheduling attributes. + * + * It is also possible to construct a set of attributes, using the most + * obviously useful properties. It is envisaged that this may be used when a + * configuration file is used to set locally sensible values. The attributes + * supported are: + * + * * attr_detached -- whether to start detached or not + * * attr_inherit_sched -- whether to inherit scheduling attributes + * * attr_sched_scope -- scheduling scope + * * attr_sched_policy -- scheduling policy + * * attr_sched_priority -- scheduling priority + * + * See qpt_thread_attr_init, below. + * + * Not supported here are: + * + * * attr_guardsize + * * attr_stack + * * attr_stacksize + * + * Pthread Mutex Attributes -- Error Checking + * ========================================== + * + * Mutexes are kept simple, only attr_type is used, and that by default. + * + * POSIX defines four types of mutex: + * + * _NORMAL no ownership check -- owner will deadlock if locks mutex ! + * -- undefined what happens if unlock + * mutex not owned by self ! + * no recursive locking + * + * _ERRORCHECK checks for ownership on lock and unlock + * no recursive locking + * + * _RECURSIVE checks for ownership on lock and unlock + * counts up locks and counts down unlocks + * + * This looks useful, but goes wrong with condition variables ! + * + * _DEFAULT undefined whether checks owner or not, on lock and/or unlock. + * no recursive locking + * + * See qpthreads.h for discussion of Quagga's standard type (QPT_MUTEX_TYPE). + * + * Other attributes are left in their default state: + * + * * attr_prioceiling -- default undefined + * * attr_protocol -- default undefined + * * attr_pshared -- defaults to _PROCESS_PRIVATE + * + * For the time being it is assumed that these are too exotic. + * + * Pthread Condition Variable Attributes + * ===================================== + * + * Condition variables have only two attributes: + * + * * attr_clock -- which clock to use + * * attr_pshared -- defaults to _PROCESS_PRIVATE + * + * The use a clock other than Quagga's standard (QPT_COND_CLOCK_ID) is possible, + * but not recommended. (See qpthreads.h for discussion of this.) + */ + +/*============================================================================== + * Thread creation and attributes. + * + * Threads may be created with a given set of attributes if required. + * + * qpt_thread_attr_init() will initialise a set of attributes including the + * current standard scheduling attributes. It is envisaged that configuration + * options may be used to specify these. + * + * qpt_thread_create() creates a thread using the given attributes. If those + * are NULL, then the system defaults are used. + */ + +/* Initialise a set of attributes -- setting the scheduling options. + * + * Options: + * + * qpt_attr_joinable -- the default if nothing specified. + * qpt_attr_detached -- overrides qpt_attr_joinable. + * + * qpt_attr_sched_inherit -- all scheduling attributes are to be inherited. + * No explicit scheduling attributes may be set. + * + * qpt_attr_sched_scope -- set explicit, given, scope. + * qpt_attr_sched_policy -- set explicit, given, policy + * qpt_attr_sched_priority -- set explicit, given, priority + * + * If none of the _sched_ options are given, then the scheduling attributes are + * left to whatever default values the system chooses. + * + * If the _sched_inherit option is specified, none of the other _sched_ options + * may be specified. + * + * If any of the explicit scheduling options are given, they are set in this + * order. If only some of these options are given, then the caller is + * assuming that the system will choose sensible defaults. + * + * The scope, policy and priority arguments are use only if the corresponding + * option is specified. + * + * Returns the address of the qpt_thread_attr_t structure. + */ +qpt_thread_attr_t* +qpt_thread_attr_init(qpt_thread_attr_t* attr, enum qpt_attr_options opts, + int scope, int policy, int priority) +{ + int err ; + + assert((opts & ~qpt_attr_known) == 0) ; + + /* Initialise thread attributes structure (allocating if required.) */ + if (attr == NULL) + attr = XMALLOC(MTYPE_QPT_THREAD_ATTR, sizeof(qpt_thread_attr_t)) ; + + err = pthread_attr_init(attr) ; + if (err != 0) + zabort_err("pthread_attr_init failed", err) ; + + /* If not qpt_attr_detached, then set joinable. */ + err = pthread_attr_setdetachstate(attr, + (opts & qpt_attr_detached) ? PTHREAD_CREATE_DETACHED + : PTHREAD_CREATE_JOINABLE) ; + if (err != 0) + zabort_err("pthread_attr_setdetachstate failed", err) ; + + /* If setting anything to do with scheduling... */ + if (opts & qpt_attr_sched_setting) + { + /* Either we inherit or we set explicit parameters. */ + + err = pthread_attr_setinheritsched(attr, + (opts & qpt_attr_sched_inherit) ? PTHREAD_INHERIT_SCHED + : PTHREAD_EXPLICIT_SCHED) ; + if (err != 0) + zabort_err("pthread_attr_setinheritsched", err) ; + + if (opts & qpt_attr_sched_inherit) + assert((opts & qpt_attr_sched_explicit) == 0) ; + else + { + if (opts & qpt_attr_sched_scope) + { + err = pthread_attr_setscope(attr, scope) ; + if (err != 0) + zabort_err("pthread_attr_setscope failed", err) ; + } ; + if (opts & qpt_attr_sched_policy) + { + err = pthread_attr_setschedpolicy(attr, scope) ; + if (err != 0) + zabort_err("pthread_attr_setschedpolicy failed", err) ; + } ; + if (opts & qpt_attr_sched_priority) + { + struct sched_param sparm ; + err = pthread_attr_getschedparam(attr, &sparm) ; + if (err != 0) + zabort_err("pthread_attr_getschedparam failed", err) ; + sparm.sched_priority = priority ; + err = pthread_attr_setschedparam(attr, &sparm) ; + if (err != 0) + zabort_err("pthread_attr_setschedparam failed", err) ; + } ; + } ; + } ; + + /* Done -- return qpt_thread_attr_t* */ + return attr ; +} ; + +/* Create Thread with given attributes (if any). + * + * If no attributes are given (attr == NULL) the thread is created with system + * default attributes -- *except* that it is created joinable. + * + * Returns the qpt_thread_t "thread id". + */ +qpt_thread_t +qpt_thread_create(void* (*start)(void*), void* arg, qpt_thread_attr_t* attr) +{ + qpt_thread_attr_t thread_attr ; + qpt_thread_t thread_id ; + int default_attr ; + int err ; + + default_attr = (attr == NULL) ; + if (default_attr) + attr = qpt_thread_attr_init(&thread_attr, qpt_attr_joinable, 0, 0, 0) ; + + err = pthread_create(&thread_id, attr, start, arg) ; + if (err != 0) + zabort_err("pthread_create failed", err) ; + + if (default_attr) + { + err = pthread_attr_destroy(attr) ; /* being tidy */ + if (err != 0) + zabort_err("pthread_attr_destroy failed", err) ; + } ; + + return thread_id ; +} ; + +/*============================================================================== + * Mutex initialise and destroy. + */ + +/* Initialise Mutex (allocating if required). + * + * Options: + * + * qpt_mutex_quagga -- see qpthreads.h for discussion of this. + * qpt_mutex_normal -- ie PTHREAD_MUTEX_NORMAL + * qpt_mutex_recursive -- ie PTHREAD_MUTEX_RECURSIVE + * qpt_mutex_errorcheck -- ie PTHREAD_MUTEX_ERRORCHECK + * qpt_mutex_default -- system default + * + * Of these _recursive is the most likely alternative to _quagga... BUT do + * remember that such mutexes DO NOT play well with condition variables. + */ +qpt_mutex_t* +qpt_mutex_init(qpt_mutex_t* mx, enum qpt_mutex_options opts) +{ + pthread_mutexattr_t mutex_attr ; + int type ; + int err ; + + if (mx == NULL) + mx = XMALLOC(MTYPE_QPT_MUTEX, sizeof(qpt_mutex_t)) ; + + /* Set up attributes so we can set the mutex type */ + err = pthread_mutexattr_init(&mutex_attr); + if (err != 0) + zabort_err("pthread_mutexattr_init failed", err) ; + + switch(opts) + { + case qpt_mutex_quagga: + type = QPT_MUTEX_TYPE ; + break ; + case qpt_mutex_normal: + type = PTHREAD_MUTEX_NORMAL ; + break ; + case qpt_mutex_recursive: + type = PTHREAD_MUTEX_RECURSIVE ; + break ; + case qpt_mutex_errorcheck: + type = PTHREAD_MUTEX_ERRORCHECK ; + break ; + case qpt_mutex_default: + type = PTHREAD_MUTEX_DEFAULT ; + break ; + default: + zabort("Invalid qpt_mutex option") ; + } ; + +#ifndef PTHREAD_MUTEXATTR_SETTYPE_MISSING + err = pthread_mutexattr_settype(&mutex_attr, type); + if (err != 0) + zabort_err("pthread_mutexattr_settype failed", err) ; +#endif + + /* Now we're ready to initialize the mutex itself */ + err = pthread_mutex_init(mx, &mutex_attr) ; + if (err != 0) + zabort_err("pthread_mutex_init failed", err) ; + + /* Be tidy with the attributes */ + err = pthread_mutexattr_destroy(&mutex_attr) ; + if (err != 0) + zabort_err("pthread_mutexattr_destroy failed", err) ; + + /* Done: return the mutex */ + return mx ; +} ; + +/* Destroy given mutex, and (if required) free it. + * + * Returns NULL. +*/ +qpt_mutex_t* +qpt_mutex_destroy(qpt_mutex_t* mx, int free_mutex) +{ + int err ; + + err = pthread_mutex_destroy(mx) ; + if (err != 0) + zabort_err("pthread_mutex_destroy failed", err) ; + + if (free_mutex) + XFREE(MTYPE_QPT_MUTEX, mx) ; + + return NULL ; +} ; + +/*============================================================================== + * Condition Variable initialise and destroy. + */ + +/* Initialise Condition Variable (allocating if required). + * + * Options: + * + * qpt_cond_quagga -- use Quagga's default clock + * qpt_cond_realtime -- force CLOCK_REALTIME + * qpt_cond_monotonic -- force CLOCK_MONOTONIC (if available) + */ +qpt_cond_t* +qpt_cond_init(qpt_cond_t* cv, enum qpt_cond_options opts) +{ + pthread_condattr_t cond_attr ; + int clock ; + int err ; + + if (cv == NULL) + cv = XMALLOC(MTYPE_QPT_COND, sizeof(qpt_cond_t)) ; + + /* Set up attributes so we can set the type */ + err = pthread_condattr_init(&cond_attr); + if (err != 0) + zabort_err("pthread_condattr_init failed", err) ; + + switch(opts) + { + case qpt_cond_quagga: + clock = QPT_COND_CLOCK_ID ; + break ; + case qpt_cond_realtime: + clock = CLOCK_REALTIME ; + break ; + case qpt_cond_monotonic: + clock = CLOCK_MONOTONIC ; + break ; + default: + zabort("Invalid qpt_cond option") ; + } ; + + err = pthread_condattr_setclock(&cond_attr, clock); + if (err != 0) + zabort_err("pthread_condattr_setclock failed", err) ; + + /* Now we're ready to initialize the condition variable itself */ + err = pthread_cond_init(cv, &cond_attr) ; + if (err != 0) + zabort_err("pthread_cond_init failed", err) ; + + /* Be tidy with the attributes */ + err = pthread_condattr_destroy(&cond_attr) ; + if (err != 0) + zabort_err("pthread_condattr_destroy failed", err) ; + + /* Done: return the condition variable */ + return cv ; +} ; + +/* Destroy given mutex, and (if required) free it. + * + * Returns NULL. +*/ +qpt_cond_t* +qpt_cond_destroy(qpt_cond_t* cv, int free_cond) +{ + int err ; + + err = pthread_cond_destroy(cv) ; + if (err != 0) + zabort_err("pthread_cond_destroy failed", err) ; + + if (free_cond) + XFREE(MTYPE_QPT_COND, cv) ; + + return NULL ; +} ; diff --git a/lib/qpthreads.h b/lib/qpthreads.h new file mode 100644 index 00000000..189eabc6 --- /dev/null +++ b/lib/qpthreads.h @@ -0,0 +1,393 @@ +/* Quagga Pthreads support -- header + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef _ZEBRA_QPTHREADS_H +#define _ZEBRA_QPTHREADS_H + +#include <stdint.h> +#include <time.h> +#include <pthread.h> +#include <unistd.h> +#include <errno.h> + +#include "zassert.h" +#include "qtime.h" + + +#ifndef Inline +#define Inline static inline +#endif + +/*============================================================================== + * Quagga Pthread Interface -- qpt_xxxx + * + * Here are captured all the pthreads features used in Quagga. + * + * This provides: + * + * * "wrappers" around functions which should not fail, but whose return + * code it is best to check... at least in a debug environment. + * + * * the possibility of a separate no pthreads build where pthread facilities + * are either dummied out or otherwise dealt with. + * + * * the ability to add any work-arounds which may be required if poorly + * conforming pthreads implementations are encountered + */ + +#if !defined(_POSIX_THREADS) || (_POSIX_THREADS <= 0) +#error Require _POSIX_THREADS +#endif + +/*============================================================================== + * TEMPORARY WORKAROUND + * + * TODO: discover why PTHREAD_MUTEX_NORMAL etc are not defined !! + * + */ + +#define PTHREAD_MUTEXATTR_SETTYPE_MISSING 1 + +#ifdef PTHREAD_MUTEXATTR_SETTYPE_MISSING +#define PTHREAD_MUTEX_NORMAL PTHREAD_MUTEX_TIMED_NP +#define PTHREAD_MUTEX_ERRORCHECK PTHREAD_MUTEX_ERRORCHECK_NP +#define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP +#define PTHREAD_MUTEX_DEFAULT PTHREAD_MUTEX_NORMAL +#endif + +/*============================================================================== + * Data types + */ + +typedef pthread_t qpt_thread_t ; +typedef pthread_mutex_t qpt_mutex_t ; +typedef pthread_cond_t qpt_cond_t ; + +typedef pthread_attr_t qpt_thread_attr_t ; + +/*============================================================================== + * Thread Creation -- see qpthreads.c for further discussion. + */ + +enum qpt_attr_options { + qpt_attr_joinable = 0, /* the default for Quagga */ + + qpt_attr_detached = 0x0001, /* otherwise will set joinable */ + + qpt_attr_sched_inherit = 0x0002, /* otherwise will use default */ + + qpt_attr_sched_scope = 0x0004, /* otherwise inherit/default */ + qpt_attr_sched_policy = 0x0008, /* otherwise inherit/default */ + qpt_attr_sched_priority = 0x0010, /* otherwise inherit/default */ +} ; + +#define qpt_attr_sched_explicit ( qpt_attr_sched_scope \ + | qpt_attr_sched_policy \ + | qpt_attr_sched_priority ) + +#define qpt_attr_sched_setting ( qpt_attr_sched_inherit \ + | qpt_attr_sched_explicit ) + +#define qpt_attr_known ( qpt_attr_detached | qpt_attr_sched_setting ) + +extern qpt_thread_attr_t* +qpt_thread_attr_init(qpt_thread_attr_t* attr, enum qpt_attr_options opts, + int scope, int policy, int priority) ; +extern qpt_thread_t +qpt_thread_create(void* (*start)(void*), void* arg, qpt_thread_attr_t* attr) ; + +/*============================================================================== + * Mutex handling. + * + * Quagga's default mutex type is: + * + * * PTHREAD_MUTEX_ERRORCHECK unless NDEBUG && NDEBUG_QPTHREADS + * * QPT_MUTEX_TYPE_DEFAULT + * + * QPT_MUTEX_TYPE_DEFAULT may be set elsewhere. If it is not set then it is + * set here to be PTHREAD_MUTEX_NORMAL. + * + * NB: on the face of it PTHREAD_MUTEX_NORMAL should be the fastest. It is + * possible that PTHREAD_MUTEX_DEFAULT may have system specific semantics + * that make it faster than the standard _NORMAL. It is also possible that + * a given system may elect to provide a safer mutex than the _NORMAL by + * default. + * + * If _DEFAULT is faster than _NORMAL, then QPT_MUTEX_TYPE_DEFAULT may be + * used to override this choice. + */ + +enum qpt_mutex_options { + qpt_mutex_quagga = 0x0000, /* Quagga's default */ + qpt_mutex_normal = 0x0001, + qpt_mutex_recursive = 0x0002, + qpt_mutex_errorcheck = 0x0003, + qpt_mutex_default = 0x0004, /* system default */ +} ; + +#ifndef QPT_MUTEX_TYPE_DEFAULT +# define QPT_MUTEX_TYPE_DEFAULT PTHREAD_MUTEX_NORMAL +#endif + +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) +# define QPT_MUTEX_TYPE QPT_MUTEX_TYPE_DEFAULT +#else +# define QPT_MUTEX_TYPE PTHREAD_MUTEX_ERRORCHECK +#endif + +extern qpt_mutex_t* +qpt_mutex_init(qpt_mutex_t* mx, enum qpt_mutex_options opts) ; + +extern qpt_mutex_t* +qpt_mutex_destroy(qpt_mutex_t* mx, int free_mutex) ; + +#define qpt_mutex_destroy_keep(mx) qpt_mutex_destroy(mx, 0) +#define qpt_mutex_destroy_free(mx) qpt_mutex_destroy(mx, 1) + +Inline void +qpt_mutex_lock(qpt_mutex_t* mx) ; /* do nothing if mx == NULL */ + +Inline int +qpt_mutex_trylock(qpt_mutex_t* mx) ; /* do nothing if mx == NULL */ + +Inline void +qpt_mutex_unlock(qpt_mutex_t* mx) ; /* do nothing if mx == NULL */ + +/*============================================================================== + * Condition Variable handling + * + * Quagga's default clock for condition variables is QPT_COND_CLOCK_ID, which + * may be set elsewhere. If it is not set then it is set here to be: + * + * * CLOCK_MONOTONIC if available + * * CLOCK_REALTIME otherwise -- this is the standard default. + * + * NB: qpt_cond_get_timeout_time uses QPT_COND_CLOCK_ID. + * + * If a specific clock is required, it can be set... but the user of the + * condition variable must take care to base time-out times on that clock. + * + * NB: static initialisation of condition variables is not supported, to avoid + * confusion between the standard default and Quagga's default. + */ + +#ifndef QPT_COND_CLOCK_ID +# ifndef HAVE_CLOCK_MONOTONIC +# define QPT_COND_CLOCK_ID CLOCK_REALTIME +# else +# define QPT_COND_CLOCK_ID CLOCK_MONOTONIC +# endif +#endif + +enum qpt_cond_options { + qpt_cond_quagga = 0x0000, /* Quagga's default */ + qpt_cond_realtime = 0x0001, /* standard default */ + qpt_cond_monotonic = 0x0002, +} ; + +extern qpt_cond_t* +qpt_cond_init(qpt_cond_t* cv, enum qpt_cond_options opts) ; + +extern qpt_cond_t* +qpt_cond_destroy(qpt_cond_t* cv, int free_cond) ; + +#define qpt_cond_destroy_keep(cv) qpt_cond_destroy(cv, 0) +#define qpt_cond_destroy_free(cv) qpt_cond_destroy(cv, 1) + +Inline void +qpt_cond_wait(qpt_cond_t* cv, qpt_mutex_t* mx) ; + +Inline qtime_t +qpt_cond_get_timeout_time(qtime_t wait) ; + +Inline int +qpt_cond_timedwait(qpt_cond_t* cv, qpt_mutex_t* mx, qtime_t tot) ; + +Inline void +qpt_cond_signal(qpt_cond_t* cv) ; + +Inline void +qpt_cond_broadcast(qpt_cond_t* cv) ; + +/*============================================================================== + * Mutex inline functions + */ + +/* Lock given mutex. + * + * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the + * return value is valid -- zabort_errno if it isn't. + */ + +Inline void +qpt_mutex_lock(qpt_mutex_t* mx) /* do nothing if mx == NULL */ +{ + if (mx != NULL) + { +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) + pthread_mutex_lock(mx) ; +#else + int err = pthread_mutex_lock(mx) ; + if (err != 0) + zabort_err("pthread_mutex_lock failed", err) ; +#endif + } ; +} ; + +/* Try to lock given mutex. + * + * Returns: lock succeeded (1 => have locked, 0 => unable to lock). + * + * Has to check the return value, so zabort_errno if not EBUSY. + */ + +Inline int +qpt_mutex_trylock(qpt_mutex_t* mx) /* do nothing if mx == NULL */ +{ + if (mx != NULL) + { + int err = pthread_mutex_trylock(mx) ; + if (err == 0) + return 1 ; /* success: it's locked. */ + if (err == EBUSY) + return 0 ; /* unable to lock */ + + zabort_err("pthread_mutex_trylock failed", err) ; + /* crunch */ + } ; +} ; + +/* Unlock given mutex. + * + * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the + * return value is valid -- zabort_errno if it isn't. + */ +Inline void +qpt_mutex_unlock(qpt_mutex_t* mx) /* do nothing if mx == NULL */ +{ + if (mx != NULL) + { +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) + pthread_mutex_unlock(mx) ; +#else + int err = pthread_mutex_lock(mx) ; + if (err != 0) + zabort_err("pthread_mutex_lock failed", err) ; +#endif + } ; +} ; + +/*============================================================================== + * Condition variable inline functions + */ + +/* Wait for given condition variable. + * + * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the + * return value is valid -- zabort_errno if it isn't. + */ + +Inline void +qpt_cond_wait(qpt_cond_t* cv, qpt_mutex_t* mx) +{ +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) + pthread_cond_wait(cv, mx) ; +#else + int err = pthread_cond_wait(cv, mx) ; + if (err != 0) + zabort_err("pthread_cond_wait failed", err) ; +#endif +} ; + +/* Get a time-out time (for use with qpt_cond_timedwait). + * + * Returns the current system time plus the given wait time. + */ + +Inline qtime_t +qpt_cond_get_timeout_time(qtime_t wait) +{ + return qt_clock_gettime(QPT_COND_CLOCK_ID) + wait ; +} ; + +/* Wait for given condition variable or time-out. + * + * Returns: wait succeeded (1 => success, 0 => timed-out). + * + * The time-out is an *absolute* time expressed as a qtime_t. + * + * NB: qpt_cond_get_timeout_time() should be used to generate the required + * time-out. That uses CLOCK_ + * + * Has to check the return value, so zabort_errno if not EBUSY. + */ + +Inline int +qpt_cond_timedwait(qpt_cond_t* cv, qpt_mutex_t* mx, qtime_t tot) +{ + struct timespec ts ; + + int err = pthread_cond_timedwait(cv, mx, qtime2timespec(&ts, tot)) ; + if (err == 0) + return 1 ; /* got condition */ + if (err == ETIMEDOUT) + return 0 ; /* got time-out */ + + zabort_err("pthread_cond_timedwait failed", err) ; + /* crunch */ +} ; + +/* Signal given condition. + * + * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the + * return value is valid -- zabort_errno if it isn't. + */ + +Inline void +qpt_cond_signal(qpt_cond_t* cv) +{ +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) + pthread_cond_signal(cv) ; +#else + int err = pthread_cond_signal(cv) ; + if (err != 0) + zabort_err("pthread_cond_signal failed", err) ; +#endif +} ; + +/* Broadcast given condition. + * + * Unless both NCHECK_QPTHREADS and NDEBUG are defined, checks that the + * return value is valid -- zabort_errno if it isn't. + */ +Inline void +qpt_cond_broadcast(qpt_cond_t* cv) +{ +#if defined(NDEBUG) && defined(NDEBUG_QPTHREADS) + pthread_cond_broadcast(cv) ; +#else + int err = pthread_cond_broadcast(cv) ; + if (err != 0) + zabort_err("pthread_cond_broadcast failed", err) ; +#endif +} ; + +#endif /* _ZEBRA_QPTHREADS_H */ diff --git a/lib/qtime.c b/lib/qtime.c new file mode 100644 index 00000000..cdcf09f9 --- /dev/null +++ b/lib/qtime.c @@ -0,0 +1,128 @@ +/* Quagga Realtime Clock handling -- functions + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#include <sys/times.h> +#include <errno.h> + +#include "zassert.h" +#include "qtime.h" + +/*============================================================================== + * This is a collection of functions and (in qtime.h) macros and inline + * functions which support system time and a monotonic clock. + */ + +/*============================================================================== + * Replacement for CLOCK_MONOTONIC. + * + * With thanks to Joakim Tjernlund for reminding everyone of the return value + * from times() ! + * + * times() is defined to return a value which is the time since some fixed time + * before the application started (or when the application started). This time + * is measured in units of sysconf(_SC_CLK_TCK) ticks per second. + * + * The only tricky bit is that the value returned (of type clock_t) is a + * signed integer, which may wrap round. It is not defined exactly how it + * does this... but it is generally assumed that this_sample - last_sample will + * give the time between the samples. + * + * The qtime_t value is in nano-seconds. + * + * The result from times() is in units of sysconf(_SC_CLK_TCK). + * + * NB: it is assumed that qt_craft_monotonic will be called often enough to + * ensure that it is not fooled by the clock wrapping round. + * + * Assuming that clock_t is a signed 32-bit integer, which is kept +ve, + * then the clock wraps round in 2^31 ticks which is: + * + * at 1,000 ticks/sec: > 24 days ! + * at 1,000,000 ticks/sec: > 35 minutes + * + * So this should be a safe assumption -- particularly as 60, 100, 250 and + * 1000 ticks per second appear to be the popular options. + * + * For safety, this asserts that the value is <= 1,000,000. + */ + +#ifdef GNU_LINUX +#define TIMES_TAKES_NULL 1 +#else +#undef TIMES_TAKES_NULL +#endif + +static uint64_t monotonic = 0 ; /* monotonic clock in _SC_CLK_TCK's */ +static uint64_t last_times_sample = 0 ; /* last value returned by times() */ + +static int64_t times_clk_tcks = 0 ; /* sysconf(_SC_CLK_TCK) */ +static qtime_t times_scale_q = 0 ; /* 10**9 / times_clk_tcks */ +static qtime_t times_scale_r = 0 ; /* 10**9 % times_clk_tcks */ + +qtime_t +qt_craft_monotonic(void) { + struct tms dummy ; + uint64_t this_times_sample ; + + /* No errors are defined for times(), but a return of -1 is defined */ + /* to indicate an error condition, with errno saying what it is ! */ + /* */ + /* The following deals carefully with this -- cannot afford for the */ + /* clock either to jump or to get stuck ! */ + +#ifdef TIMES_TAKES_NULL + this_times_sample = times(NULL) ; /* assume this saves effort ! */ +#else + this_times_sample = times(&dummy) ; +#endif + + if (this_times_sample == (clock_t)-1) + { + errno = 0 ; + this_times_sample = times(&dummy) ; + if (errno != 0) + zabort_errno("times() failed") ; + } ; + + + if (times_clk_tcks == 0) /* Is zero until it's initialized */ + { + lldiv_t qr ; + confirm(sizeof(qtime_t) <= sizeof(long long int)) ; + + times_clk_tcks = sysconf(_SC_CLK_TCK) ; + passert((times_clk_tcks > 0) && (times_clk_tcks <= 1000000)) ; + + qr = lldiv(QTIME_SECOND, times_clk_tcks) ; + times_scale_q = qr.quot ; + times_scale_r = qr.rem ; + + last_times_sample = this_times_sample ; + } ; + + monotonic += (this_times_sample - last_times_sample) ; + + if (times_scale_r == 0) + return monotonic * times_scale_q ; + else + return (monotonic * times_scale_q) + + ((monotonic * times_scale_r) / times_clk_tcks) ; +} ; diff --git a/lib/qtime.h b/lib/qtime.h new file mode 100644 index 00000000..a9e635d1 --- /dev/null +++ b/lib/qtime.h @@ -0,0 +1,213 @@ +/* Quagga Realtime Clock handling -- header + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef _ZEBRA_QTIME_H +#define _ZEBRA_QTIME_H + +#include <stdint.h> +#include <stdlib.h> +#include <time.h> +#include <sys/time.h> +#include <unistd.h> + +#include "zassert.h" +#include "config.h" + +#ifndef Inline +#define Inline static inline +#endif + +/*============================================================================== + * qtime_t -- signed 64-bit integer. + * + * The various time functions work in terms of the structures: + * + * timespec -- tv_secs seconds + * tv_nsecs nano-seconds + * + * timeval -- tv_secs seconds + * tv_usecs micro-seconds + * + * Given a 64-bit integer it is much easier to do operations on a 64 bit + * (signed) nano-second value. That gives 34 bits for the seconds count, which + * is > 290 years. + */ + +typedef int64_t qtime_t ; + +/* A qtime_t second 123456789 -- nano-seconds */ +#define QTIME_SECOND 1000000000 +#define TIMESPEC_SECOND 1000000000 +#define TIMEVAL_SECOND 1000000 + +/* Macro to convert time in seconds to a qtime_t */ +#define QTIME(s) ((qtime_t)((s) * QTIME_SECOND)) + +Inline qtime_t +timespec2qtime(struct timespec* p_ts) ; + +Inline qtime_t +timeval2qtime(struct timeval* p_tv) ; + +Inline struct timespec* +qtime2timespec(struct timespec* p_ts, qtime_t qt) ; + +Inline struct timeval* +qtime2timeval(struct timeval* p_tv, qtime_t qt) ; + +/*============================================================================== + * Clocks. + * + * Here is support for: + * + * * System Clock + * + * This can be read using either clock_gettime(CLOCK_REALTIME, &ts) or + * gettimeofday(&tv, NULL) -- which (are believed to) return the same clock, + * but in different units. + * + * * Monotonic Clock + * + * Using clock_gettime(CLOCK_MONOTONIC, &ts) if it is available, otherwise + * a manufactured equivalent using times(). + */ + +Inline qtime_t +qt_get_timeofday(void) ; /* gettimeofday(&tv, NULL) */ + +Inline qtime_t +qt_get_realtime(void) ; /* clock_gettime(CLOCK_REALTIME, &ts) */ + +Inline qtime_t +qt_get_monotonic(void) ; /* clock_gettime(CLOCK_MONOTONIC, &ts */ + /* OR equivalent using times() */ + +/* Function to manufacture a monotonic clock. */ +extern qtime_t qt_craft_monotonic(void) ; + +/*============================================================================== + * Inline conversion functions + */ + +/* Convert timespec to qtime_t + * + * Returns qtime_t value. + */ +Inline qtime_t +timespec2qtime(struct timespec* p_ts) +{ + return ((qtime_t)(p_ts->tv_sec) * QTIME_SECOND) + p_ts->tv_nsec ; +} ; + +/* Convert timeval to qtime_t + * + * Returns qtime_t value. + */ +Inline qtime_t +timeval2qtime(struct timeval* p_tv) +{ + return ((qtime_t)(p_tv->tv_sec) * QTIME_SECOND) + (p_tv->tv_usec * 1000) ; +} ; + +/* Convert qtime_t to timespec + * + * Takes address of struct timespec and returns that address. + */ +Inline struct timespec* +qtime2timespec(struct timespec* p_ts, qtime_t qt) +{ + lldiv_t imd = lldiv(qt, QTIME_SECOND) ; + p_ts->tv_sec = imd.quot ; + p_ts->tv_nsec = imd.rem ; + + return p_ts ; +} ; + +/* Convert timespec to qtime_t + * + * Takes address of struct timespec and returns that address. + */ +Inline struct timeval* +qtime2timeval(struct timeval* p_tv, qtime_t qt) +{ + lldiv_t imd = lldiv(qt, QTIME_SECOND) ; + p_tv->tv_sec = imd.quot ; + p_tv->tv_usec = imd.rem / 1000 ; + + return p_tv ; +} ; + +/*============================================================================== + * Inline Clock Functions. + */ + +/* Read given clock & return a qtime_t value. + * + * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + */ + +Inline qtime_t +qt_clock_gettime(clockid_t clock_id) +{ + struct timespec ts ; + + if (clock_gettime(clock_id, &ts) != 0) + zabort_errno("clock_gettime failed") ; + + return timespec2qtime(&ts) ; +} ; + +/* gettimeofday(&tv, NULL) -- returning qtime_t value + */ +Inline qtime_t +qt_get_timeofday(void) +{ + struct timeval tv ; + gettimeofday(&tv, NULL) ; + return timeval2qtime(&tv) ; +} + +/* clock_gettime(CLOCK_REALTIME, &ts) -- returning qtime_t value + * + * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + */ +Inline qtime_t +qt_get_realtime(void) +{ + return qt_clock_gettime(CLOCK_REALTIME) ; +} ; + +/* clock_gettime(CLOCK_MONOTONIC, &ts) OR qt_craft_monotonic() + * -- returning qtime_t value + * + * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + */ +Inline qtime_t +qt_get_monotonic(void) +{ +#ifdef HAVE_CLOCK_MONOTONIC + return qt_clock_gettime(CLOCK_MONOTONIC) ; +#else + return qt_craft_monotonic() ; +#endif +} ; + +#endif /* _ZEBRA_QTIME_H */ diff --git a/lib/zassert.h b/lib/zassert.h index 79126760..26b67da6 100644 --- a/lib/zassert.h +++ b/lib/zassert.h @@ -21,7 +21,45 @@ extern void _zlog_assert_failed (const char *assertion, const char *file, (_zlog_assert_failed(#EX, __FILE__, __LINE__, \ __ASSERT_FUNCTION), 0))) +/* Implicitly *permanent* assert() -- irrespective of NDEBUG */ #undef assert #define assert(EX) zassert(EX) +/* Explicitly permanent assert() */ +#define passert(EX) zassert(EX) + +/* NDEBUG time assert() */ +#ifndef NDEBUG +#define dassert(EX) zassert(EX) +#else +#define dassert(EX) +#endif + +/* TODO: implement _zlog_abort() to give required messages */ + +/* Abort with message */ +#define zabort(MS) _zlog_assert_failed(MS, __FILE__, __LINE__, \ + __ASSERT_FUNCTION) + +/* Abort with message and errno and strerror() thereof */ +#define zabort_errno(MS) _zlog_assert_failed(MS, __FILE__, __LINE__, \ + __ASSERT_FUNCTION) + +/* Abort with message and given error and strerror() thereof */ +#define zabort_err(MS, ERR) _zlog_assert_failed(MS, __FILE__, __LINE__, \ + __ASSERT_FUNCTION) + +/*============================================================================== + * Compile time CONFIRM gizmo + * + * Two forms: CONFIRM(e) for use at top (file) level + * confirm(e) for use inside compound statements + */ +#ifndef CONFIRM + + #define CONFIRM(e) extern void CONFIRMATION(char CONFIRM[(e) ? 1 : -1]) ; + #define confirm(e) { CONFIRM(e) } + +#endif + #endif /* _QUAGGA_ASSERT_H */ |