diff --git a/include/qb/qblist.h b/include/qb/qblist.h index 63c39e9..6e571de 100644 --- a/include/qb/qblist.h +++ b/include/qb/qblist.h @@ -1,247 +1,310 @@ /* * Copyright (C) 2006-2010, 2009 Red Hat, Inc. * * Author: Steven Dake * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #ifndef QB_LIST_H_DEFINED #define QB_LIST_H_DEFINED /* *INDENT-OFF* */ #ifdef __cplusplus extern "C" { #endif /* *INDENT-ON* */ #include #include /** * @file qblist.h * This is a kernel style list implementation. * * @author Steven Dake */ struct qb_list_head { struct qb_list_head *next; struct qb_list_head *prev; }; /** * @def QB_LIST_DECLARE() * Declare and initialize a list head. */ #define QB_LIST_DECLARE(name) \ struct qb_list_head name = { &(name), &(name) } #define QB_INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0) /** * Initialize the list entry. * * Points next and prev pointers to head. * @param head pointer to the list head */ static inline void qb_list_init(struct qb_list_head *head) { head->next = head; head->prev = head; } /** * Add this element to the list. * * @param element the new element to insert. * @param head pointer to the list head */ static inline void qb_list_add(struct qb_list_head *element, struct qb_list_head *head) { head->next->prev = element; element->next = head->next; element->prev = head; head->next = element; } /** * Add to the list (but at the end of the list). * * @param element pointer to the element to add * @param head pointer to the list head * @see qb_list_add() */ static inline void qb_list_add_tail(struct qb_list_head *element, struct qb_list_head *head) { head->prev->next = element; element->next = head; element->prev = head->prev; head->prev = element; } /** * Delete an entry from the list. * * @param _remove the list item to remove */ static inline void qb_list_del(struct qb_list_head *_remove) { _remove->next->prev = _remove->prev; _remove->prev->next = _remove->next; } +/** + * Replace old entry by new one + * @param old: the element to be replaced + * @param new: the new element to insert + */ +static inline void qb_list_replace(struct qb_list_head *old, + struct qb_list_head *new) +{ + new->next = old->next; + new->next->prev = new; + new->prev = old->prev; + new->prev->next = new; +} + +/** + * Tests whether list is the last entry in list head + * @param list: the entry to test + * @param head: the head of the list + * @return boolean true/false + */ +static inline int qb_list_is_last(const struct qb_list_head *list, + const struct qb_list_head *head) +{ + return list->next == head; +} + /** * A quick test to see if the list is empty (pointing to it's self). * @param head pointer to the list head * @return boolean true/false */ static inline int32_t qb_list_empty(const struct qb_list_head *head) { return head->next == head; } /** * Join two lists. * @param list the new list to add. * @param head the place to add it in the first list. * * @note The "list" is reinitialised */ static inline void qb_list_splice(struct qb_list_head *list, struct qb_list_head *head) { struct qb_list_head *first = list->next; struct qb_list_head *last = list->prev; struct qb_list_head *at = head->next; first->prev = head; head->next = first; last->next = at; at->prev = last; } +/** + * Join two lists, each list being a queue + * @param list: the new list to add. + * @param head: the place to add it in the first list. + */ +static inline void qb_list_splice_tail(struct qb_list_head *list, + struct qb_list_head *head) +{ + struct qb_list_head *first = list->next; + struct qb_list_head *last = list->prev; + struct qb_list_head *at = head; + + first->prev = head->prev; + head->prev->next = first; + + last->next = at; + at->prev = last; +} + /** * Get the struct for this entry * @param ptr: the &struct list_head pointer. * @param type: the type of the struct this is embedded in. * @param member: the name of the list_struct within the struct. */ #define qb_list_entry(ptr,type,member)\ ((type *)((char *)(ptr)-(char*)(&((type *)0)->member))) +/** + * Get the first element from a list + * @param ptr: the &struct list_head pointer. + * @param type: the type of the struct this is embedded in. + * @param member: the name of the list_struct within the struct. + */ +#define qb_list_first_entry(ptr, type, member) \ + qb_list_entry((ptr)->next, type, member) /** * Iterate over a list * @param pos: the &struct list_head to use as a loop counter. * @param head: the head for your list. */ #define qb_list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) /** * Iterate over a list backwards * @param pos: the &struct list_head to use as a loop counter. * @param head: the head for your list. */ #define qb_list_for_each_reverse(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev) /** * Iterate over a list safe against removal of list entry * @param pos: the &struct list_head to use as a loop counter. * @param n: another &struct list_head to use as temporary storage * @param head: the head for your list. */ #define qb_list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) /** * Iterate over list of given type * @param pos: the type * to use as a loop counter. * @param head: the head for your list. * @param member: the name of the list_struct within the struct. */ #define qb_list_for_each_entry(pos, head, member) \ for (pos = qb_list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = qb_list_entry(pos->member.next, typeof(*pos), member)) /** * Iterate backwards over list of given type. * @param pos: the type to use as a loop counter. * @param head: the head for your list. * @param member: the name of the list_struct within the struct. */ #define qb_list_for_each_entry_reverse(pos, head, member) \ for (pos = qb_list_entry((head)->prev, typeof(*pos), member); \ &pos->member != (head); \ pos = qb_list_entry(pos->member.prev, typeof(*pos), member)) /** * Iterate over list of given type safe against removal of list entry * @param pos: the type * to use as a loop cursor. * @param n: another type * to use as temporary storage * @param head: the head for your list. * @param member: the name of the list_struct within the struct. */ #define qb_list_for_each_entry_safe(pos, n, head, member) \ for (pos = qb_list_entry((head)->next, typeof(*pos), member), \ n = qb_list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = qb_list_entry(n->member.next, typeof(*n), member)) /** * Iterate backwards over list safe against removal * @param pos: the type * to use as a loop cursor. * @param n: another type * to use as temporary storage * @param head: the head for your list. * @param member: the name of the list_struct within the struct. */ #define qb_list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = qb_list_entry((head)->prev, typeof(*pos), member), \ n = qb_list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = qb_list_entry(n->member.prev, typeof(*n), member)) +/** + * Iterate over list of given type from the current point + * @param pos: the type * to use as a loop cursor. + * @param head: the head for your list. + * @param member: the name of the list_struct within the struct. + */ +#define qb_list_for_each_entry_from(pos, head, member) \ + for (; &pos->member != (head); \ + pos = qb_list_entry(pos->member.next, typeof(*pos), member)) + /** * Count the number of items in the list. * @param head: the head for your list. * @return length of the list. */ static inline int32_t qb_list_length(struct qb_list_head *head) { struct qb_list_head *item; int32_t length = 0; qb_list_for_each(item, head) length++; return length; } /* *INDENT-OFF* */ #ifdef __cplusplus } #endif /* __cplusplus */ /* *INDENT-ON* */ #endif /* QB_LIST_H_DEFINED */ diff --git a/include/tlist.h b/include/tlist.h index 18b6f6e..bc49a85 100644 --- a/include/tlist.h +++ b/include/tlist.h @@ -1,230 +1,219 @@ /* * Copyright (c) 2006-2007, 2009 Red Hat, Inc. * * Author: Steven Dake * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #ifndef QB_TLIST_H_DEFINED #define QB_TLIST_H_DEFINED #include "os_base.h" #include #include #include #ifndef TIMER_HANDLE typedef void *timer_handle; #define TIMER_HANDLE #endif static int64_t timerlist_hertz; struct timerlist { struct qb_list_head timer_head; - struct qb_list_head *timer_iter; }; struct timerlist_timer { struct qb_list_head list; uint64_t expire_time; int32_t is_absolute_timer; void (*timer_fn) (void *data); void *data; timer_handle handle_addr; }; static inline void timerlist_init(struct timerlist *timerlist) { qb_list_init(&timerlist->timer_head); timerlist_hertz = qb_util_nano_monotonic_hz(); } static inline void timerlist_add(struct timerlist *timerlist, struct timerlist_timer *timer) { struct qb_list_head *timer_list = 0; struct timerlist_timer *timer_from_list; int32_t found; - for (found = 0, timer_list = timerlist->timer_head.next; - timer_list != &timerlist->timer_head; - timer_list = timer_list->next) { + found = 0; + qb_list_for_each(timer_list, &timerlist->timer_head) { timer_from_list = qb_list_entry(timer_list, struct timerlist_timer, list); if (timer_from_list->expire_time > timer->expire_time) { - qb_list_add(&timer->list, timer_list->prev); + qb_list_add_tail(&timer->list, timer_list); found = 1; break; /* for timer iteration */ } } if (found == 0) { - qb_list_add(&timer->list, timerlist->timer_head.prev); + qb_list_add_tail(&timer->list, &timerlist->timer_head); } } static inline int32_t timerlist_add_duration(struct timerlist *timerlist, void (*timer_fn) (void *data), void *data, uint64_t nano_duration, timer_handle * handle) { struct timerlist_timer *timer; timer = (struct timerlist_timer *)malloc(sizeof(struct timerlist_timer)); if (timer == 0) { return -ENOMEM; } timer->expire_time = qb_util_nano_current_get() + nano_duration; timer->is_absolute_timer = 0; timer->data = data; timer->timer_fn = timer_fn; timer->handle_addr = handle; timerlist_add(timerlist, timer); *handle = timer; return (0); } static inline void timerlist_del(struct timerlist *timerlist, timer_handle _timer_handle) { struct timerlist_timer *timer = (struct timerlist_timer *)_timer_handle; memset(timer->handle_addr, 0, sizeof(struct timerlist_timer *)); - /* - * If the next timer after the currently expiring timer because - * timerlist_del is called from a timer handler, get to the next - * timer - */ - if (timerlist->timer_iter == &timer->list) { - timerlist->timer_iter = timerlist->timer_iter->next; - } qb_list_del(&timer->list); qb_list_init(&timer->list); free(timer); } static inline uint64_t timerlist_expire_time(struct timerlist *timerlist, timer_handle _timer_handle) { struct timerlist_timer *timer = (struct timerlist_timer *)_timer_handle; return (timer->expire_time); } static inline void timerlist_pre_dispatch(struct timerlist *timerlist, timer_handle _timer_handle) { struct timerlist_timer *timer = (struct timerlist_timer *)_timer_handle; memset(timer->handle_addr, 0, sizeof(struct timerlist_timer *)); qb_list_del(&timer->list); qb_list_init(&timer->list); } static inline void timerlist_post_dispatch(struct timerlist *timerlist, timer_handle _timer_handle) { struct timerlist_timer *timer = (struct timerlist_timer *)_timer_handle; free(timer); } /* * returns the number of msec until the next timer will expire for use with poll */ static inline uint64_t timerlist_msec_duration_to_expire(struct timerlist *timerlist) { struct timerlist_timer *timer_from_list; volatile uint64_t current_time; volatile uint64_t msec_duration_to_expire; /* * empty list, no expire */ - if (timerlist->timer_head.next == &timerlist->timer_head) { + if (qb_list_empty(&timerlist->timer_head)) { return (-1); } - timer_from_list = qb_list_entry(timerlist->timer_head.next, + timer_from_list = qb_list_first_entry(&timerlist->timer_head, struct timerlist_timer, list); if (timer_from_list->is_absolute_timer) { current_time = qb_util_nano_from_epoch_get(); } else { current_time = qb_util_nano_current_get(); } /* * timer at head of list is expired, zero msecs required */ if (timer_from_list->expire_time < current_time) { return (0); } msec_duration_to_expire = ((timer_from_list->expire_time - current_time) / QB_TIME_NS_IN_MSEC) + (1000 / timerlist_hertz); return (msec_duration_to_expire); } /* * Expires any timers that should be expired */ static inline void timerlist_expire(struct timerlist *timerlist) { struct timerlist_timer *timer_from_list; + struct qb_list_head *pos; + struct qb_list_head *next; uint64_t current_time_from_epoch; uint64_t current_monotonic_time; uint64_t current_time; current_monotonic_time = qb_util_nano_current_get(); current_time_from_epoch = current_time = qb_util_nano_from_epoch_get(); - for (timerlist->timer_iter = timerlist->timer_head.next; - timerlist->timer_iter != &timerlist->timer_head;) { + qb_list_for_each_safe(pos, next, &timerlist->timer_head) { - timer_from_list = qb_list_entry(timerlist->timer_iter, + timer_from_list = qb_list_entry(pos, struct timerlist_timer, list); current_time = (timer_from_list-> is_absolute_timer ? current_time_from_epoch : current_monotonic_time); if (timer_from_list->expire_time < current_time) { - timerlist->timer_iter = timerlist->timer_iter->next; timerlist_pre_dispatch(timerlist, timer_from_list); timer_from_list->timer_fn(timer_from_list->data); timerlist_post_dispatch(timerlist, timer_from_list); } else { break; /* for timer iteration */ } } - timerlist->timer_iter = 0; } #endif /* QB_TLIST_H_DEFINED */ diff --git a/lib/hashtable.c b/lib/hashtable.c index 492cc88..532bcc1 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -1,479 +1,472 @@ /* * Copyright (C) 2010 Red Hat, Inc. * * Author: Steven Dake * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include #include "util_int.h" #include "map_int.h" #include #define FNV_32_PRIME ((uint32_t)0x01000193) struct hash_node { struct qb_list_head list; void *value; const char *key; uint32_t refcount; struct qb_list_head notifier_head; }; struct hash_bucket { struct qb_list_head list_head; }; struct hash_table { struct qb_map map; size_t count; uint32_t order; uint32_t hash_buckets_len; struct hash_bucket hash_buckets[0]; struct qb_list_head notifier_head; }; struct hashtable_iter { struct qb_map_iter i; struct hash_node *node; uint32_t bucket; }; static void hashtable_notify(struct hash_table *t, struct hash_node *n, uint32_t event, const char *key, void *old_value, void *value); static uint32_t hash_fnv(const void *value, uint32_t valuelen, uint32_t order) { uint8_t *cd = (uint8_t *) value; uint8_t *ed = (uint8_t *) value + valuelen; uint32_t hash_result = 0x811c9dc5; int32_t res; while (cd < ed) { hash_result ^= *cd; hash_result *= FNV_32_PRIME; cd++; } res = ((hash_result >> order) ^ hash_result) & ((1 << order) - 1); return (res); } static uint32_t qb_hash_string(const void *key, uint32_t order) { char *str = (char *)key; return hash_fnv(key, strlen(str), order); } static struct hash_node * hashtable_lookup(struct hash_table *t, const char *key) { uint32_t hash_entry; struct qb_list_head *list; struct hash_node *hash_node; hash_entry = qb_hash_string(key, t->order); - for (list = t->hash_buckets[hash_entry].list_head.next; - list != &t->hash_buckets[hash_entry].list_head; - list = list->next) { + qb_list_for_each(list, &t->hash_buckets[hash_entry].list_head) { hash_node = qb_list_entry(list, struct hash_node, list); if (strcmp(hash_node->key, key) == 0) { return hash_node; } } return NULL; } static void * hashtable_get(struct qb_map *map, const char *key) { struct hash_table *t = (struct hash_table *)map; struct hash_node *n = hashtable_lookup(t, key); if (n) { return n->value; } return NULL; } static void hashtable_node_deref(struct qb_map *map, struct hash_node *hash_node) { struct hash_table *t = (struct hash_table *)map; hash_node->refcount--; if (hash_node->refcount > 0) { return; } hashtable_notify(t, hash_node, QB_MAP_NOTIFY_DELETED, hash_node->key, hash_node->value, NULL); qb_list_del(&hash_node->list); free(hash_node); } static int32_t hashtable_rm_with_hash(struct qb_map *map, const char *key, uint32_t hash_entry) { struct hash_table *hash_table = (struct hash_table *)map; struct qb_list_head *list; + struct qb_list_head *next; struct hash_node *hash_node; - for (list = hash_table->hash_buckets[hash_entry].list_head.next; - list != &hash_table->hash_buckets[hash_entry].list_head; - list = list->next) { + qb_list_for_each_safe(list, next, + &hash_table->hash_buckets[hash_entry].list_head) { hash_node = qb_list_entry(list, struct hash_node, list); if (strcmp(hash_node->key, key) == 0) { hashtable_node_deref(map, hash_node); hash_table->count--; return QB_TRUE; } } return QB_FALSE; } static int32_t hashtable_rm(struct qb_map *map, const char *key) { struct hash_table *hash_table = (struct hash_table *)map; uint32_t hash_entry; hash_entry = qb_hash_string(key, hash_table->order); return hashtable_rm_with_hash(map, key, hash_entry); } static void hashtable_put(struct qb_map *map, const char *key, const void *value) { struct hash_table *hash_table = (struct hash_table *)map; uint32_t hash_entry; struct hash_node *hash_node = NULL; struct hash_node *node_try; struct qb_list_head *list; hash_entry = qb_hash_string(key, hash_table->order); - for (list = hash_table->hash_buckets[hash_entry].list_head.next; - list != &hash_table->hash_buckets[hash_entry].list_head; - list = list->next) { + qb_list_for_each(list, &hash_table->hash_buckets[hash_entry].list_head) { node_try = qb_list_entry(list, struct hash_node, list); if (strcmp(node_try->key, key) == 0) { hash_node = node_try; break; } } if (hash_node == NULL) { hash_node = calloc(1, sizeof(struct hash_node)); if (hash_node == NULL) { errno = ENOMEM; return; } hash_table->count++; hash_node->refcount = 1; hash_node->key = key; hash_node->value = (void *)value; qb_list_init(&hash_node->list); qb_list_add_tail(&hash_node->list, &hash_table->hash_buckets[hash_entry]. list_head); qb_list_init(&hash_node->notifier_head); hashtable_notify(hash_table, hash_node, QB_MAP_NOTIFY_INSERTED, hash_node->key, NULL, hash_node->value); } else { char *old_k = (char *)hash_node->key; char *old_v = (void *)hash_node->value; hash_node->key = key; hash_node->value = (void *)value; hashtable_notify(hash_table, hash_node, QB_MAP_NOTIFY_REPLACED, old_k, old_v, hash_node->value); } } static void hashtable_notify(struct hash_table *t, struct hash_node *n, uint32_t event, const char *key, void *old_value, void *value) { struct qb_list_head *list; struct qb_map_notifier *tn; - for (list = n->notifier_head.next; - list != &n->notifier_head; list = list->next) { + qb_list_for_each(list, &n->notifier_head) { tn = qb_list_entry(list, struct qb_map_notifier, list); if (tn->events & event) { tn->callback(event, (char *)key, old_value, value, tn->user_data); } } - for (list = t->notifier_head.next; - list != &t->notifier_head; list = list->next) { + qb_list_for_each(list, &t->notifier_head) { tn = qb_list_entry(list, struct qb_map_notifier, list); if (tn->events & event) { tn->callback(event, (char *)key, old_value, value, tn->user_data); } if (((event & QB_MAP_NOTIFY_DELETED) || (event & QB_MAP_NOTIFY_REPLACED)) && (tn->events & QB_MAP_NOTIFY_FREE)) { tn->callback(QB_MAP_NOTIFY_FREE, (char *)key, old_value, value, tn->user_data); } } } static int32_t hashtable_notify_add(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, void *user_data) { struct hash_table *t = (struct hash_table *)m; struct qb_map_notifier *f; struct hash_node *n; struct qb_list_head *head = NULL; struct qb_list_head *list; int add_to_tail = QB_FALSE; if (key) { n = hashtable_lookup(t, key); if (n) { head = &n->notifier_head; } } else { head = &t->notifier_head; } if (head == NULL) { return -ENOENT; } if (events & QB_MAP_NOTIFY_FREE) { add_to_tail = QB_TRUE; } - for (list = head->next; list != head; list = list->next) { + qb_list_for_each(list, head) { f = qb_list_entry(list, struct qb_map_notifier, list); if (events & QB_MAP_NOTIFY_FREE && f->events == events) { /* only one free notifier */ return -EEXIST; } if (f->events == events && f->user_data == user_data && f->callback == fn) { return -EEXIST; } } f = malloc(sizeof(struct qb_map_notifier)); if (f == NULL) { return -errno; } f->events = events; f->user_data = user_data; f->callback = fn; qb_list_init(&f->list); if (add_to_tail) { qb_list_add_tail(&f->list, head); } else { qb_list_add(&f->list, head); } return 0; } static int32_t hashtable_notify_del(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, int32_t cmp_userdata, void *user_data) { struct hash_table *t = (struct hash_table *)m; struct qb_map_notifier *f; struct hash_node *n; struct qb_list_head *head = NULL; struct qb_list_head *list; struct qb_list_head *next; int32_t found = QB_FALSE; if (key) { n = hashtable_lookup(t, key); if (n) { head = &n->notifier_head; } } else { head = &t->notifier_head; } if (head == NULL) { return -ENOENT; } - for (list = head->next; list != head; list = next) { + qb_list_for_each_safe(list, next, head) { f = qb_list_entry(list, struct qb_map_notifier, list); - next = list->next; if (f->events == events && f->callback == fn) { if (cmp_userdata && (f->user_data == user_data)) { found = QB_TRUE; qb_list_del(&f->list); free(f); } else if (!cmp_userdata) { found = QB_TRUE; qb_list_del(&f->list); free(f); } } } if (found) { return 0; } else { return -ENOENT; } } static size_t hashtable_count_get(struct qb_map *map) { struct hash_table *hash_table = (struct hash_table *)map; return hash_table->count; } static qb_map_iter_t * hashtable_iter_create(struct qb_map *map, const char *prefix) { struct hashtable_iter *i = malloc(sizeof(struct hashtable_iter)); if (i == NULL) { return NULL; } i->i.m = map; i->node = NULL; i->bucket = 0; return (qb_map_iter_t *) i; } static const char * hashtable_iter_next(qb_map_iter_t * it, void **value) { struct hashtable_iter *hi = (struct hashtable_iter *)it; struct hash_table *hash_table = (struct hash_table *)hi->i.m; struct qb_list_head *ln; struct hash_node *hash_node = NULL; int found = QB_FALSE; int cont = QB_TRUE; int b; if (hi->node == NULL) { cont = QB_FALSE; } for (b = hi->bucket; b < hash_table->hash_buckets_len && !found; b++) { if (cont) { - ln = hi->node->list.next; + ln = &hi->node->list; cont = QB_FALSE; } else { - ln = hash_table->hash_buckets[b].list_head.next; + ln = &hash_table->hash_buckets[b].list_head; } - for (; ln != &hash_table->hash_buckets[b].list_head; - ln = ln->next) { - hash_node = qb_list_entry(ln, struct hash_node, list); + hash_node = qb_list_first_entry(ln, struct hash_node, list); + qb_list_for_each_entry_from(hash_node, + &hash_table->hash_buckets[b].list_head, list) { if (hash_node->refcount > 0) { found = QB_TRUE; hash_node->refcount++; hi->bucket = b; *value = hash_node->value; break; } } } if (hi->node) { hashtable_node_deref(hi->i.m, hi->node); } if (!found) { return NULL; } hi->node = hash_node; return hash_node->key; } static void hashtable_iter_free(qb_map_iter_t * i) { free(i); } static void hashtable_destroy(struct qb_map *map) { struct hash_table *hash_table = (struct hash_table *)map; free(hash_table); } qb_map_t * qb_hashtable_create(size_t max_size) { int32_t i; int32_t order; int32_t n = max_size; uint64_t size; struct hash_table *ht; for (i = 0; n; i++) { n >>= 1; } order = QB_MAX(i, 3); size = sizeof(struct hash_table) + (sizeof(struct hash_bucket) * (1 << order)); ht = calloc(1, size); if (ht == NULL) { return NULL; } ht->map.put = hashtable_put; ht->map.get = hashtable_get; ht->map.rm = hashtable_rm; ht->map.count_get = hashtable_count_get; ht->map.iter_create = hashtable_iter_create; ht->map.iter_next = hashtable_iter_next; ht->map.iter_free = hashtable_iter_free; ht->map.destroy = hashtable_destroy; ht->map.notify_add = hashtable_notify_add; ht->map.notify_del = hashtable_notify_del; ht->count = 0; ht->order = order; qb_list_init(&ht->notifier_head); ht->hash_buckets_len = 1 << order; for (i = 0; i < ht->hash_buckets_len; i++) { qb_list_init(&ht->hash_buckets[i].list_head); } return (qb_map_t *) ht; } diff --git a/lib/ipcs.c b/lib/ipcs.c index 544ef4a..076df4f 100644 --- a/lib/ipcs.c +++ b/lib/ipcs.c @@ -1,879 +1,874 @@ /* * Copyright (C) 2010 Red Hat, Inc. * * Author: Angus Salkeld * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include "util_int.h" #include "ipc_int.h" #include #include #include static void qb_ipcs_flowcontrol_set(struct qb_ipcs_connection *c, int32_t fc_enable); static int32_t new_event_notification(struct qb_ipcs_connection * c); static QB_LIST_DECLARE(qb_ipc_services); qb_ipcs_service_t * qb_ipcs_create(const char *name, int32_t service_id, enum qb_ipc_type type, struct qb_ipcs_service_handlers *handlers) { struct qb_ipcs_service *s; s = calloc(1, sizeof(struct qb_ipcs_service)); if (s == NULL) { return NULL; } if (type == QB_IPC_NATIVE) { #ifdef DISABLE_IPC_SHM s->type = QB_IPC_SOCKET; #else s->type = QB_IPC_SHM; #endif /* DISABLE_IPC_SHM */ } else { s->type = type; } s->pid = getpid(); s->needs_sock_for_poll = QB_FALSE; s->poll_priority = QB_LOOP_MED; s->ref_count = 1; s->service_id = service_id; (void)strlcpy(s->name, name, NAME_MAX); s->serv_fns.connection_accept = handlers->connection_accept; s->serv_fns.connection_created = handlers->connection_created; s->serv_fns.msg_process = handlers->msg_process; s->serv_fns.connection_closed = handlers->connection_closed; s->serv_fns.connection_destroyed = handlers->connection_destroyed; qb_list_init(&s->connections); qb_list_init(&s->list); qb_list_add(&s->list, &qb_ipc_services); return s; } void qb_ipcs_poll_handlers_set(struct qb_ipcs_service *s, struct qb_ipcs_poll_handlers *handlers) { s->poll_fns.job_add = handlers->job_add; s->poll_fns.dispatch_add = handlers->dispatch_add; s->poll_fns.dispatch_mod = handlers->dispatch_mod; s->poll_fns.dispatch_del = handlers->dispatch_del; } int32_t qb_ipcs_run(struct qb_ipcs_service *s) { int32_t res = 0; if (s->poll_fns.dispatch_add == NULL || s->poll_fns.dispatch_mod == NULL || s->poll_fns.dispatch_del == NULL) { return -EINVAL; } switch (s->type) { case QB_IPC_SOCKET: qb_ipcs_us_init((struct qb_ipcs_service *)s); break; case QB_IPC_SHM: #ifdef DISABLE_IPC_SHM res = -ENOTSUP; #else qb_ipcs_shm_init((struct qb_ipcs_service *)s); #endif /* DISABLE_IPC_SHM */ break; case QB_IPC_POSIX_MQ: case QB_IPC_SYSV_MQ: res = -ENOTSUP; break; default: res = -EINVAL; break; } if (res < 0) { qb_ipcs_unref(s); return res; } res = qb_ipcs_us_publish(s); if (res < 0) { (void)qb_ipcs_us_withdraw(s); qb_ipcs_unref(s); return res; } return res; } static int32_t _modify_dispatch_descriptor_(struct qb_ipcs_connection *c) { qb_ipcs_dispatch_mod_fn disp_mod = c->service->poll_fns.dispatch_mod; if (c->service->type == QB_IPC_SOCKET) { return disp_mod(c->service->poll_priority, c->event.u.us.sock, c->poll_events, c, qb_ipcs_dispatch_connection_request); } else { return disp_mod(c->service->poll_priority, c->setup.u.us.sock, c->poll_events, c, qb_ipcs_dispatch_connection_request); } return -EINVAL; } void qb_ipcs_request_rate_limit(struct qb_ipcs_service *s, enum qb_ipcs_rate_limit rl) { struct qb_ipcs_connection *c; enum qb_loop_priority old_p = s->poll_priority; struct qb_list_head *pos; struct qb_list_head *n; switch (rl) { case QB_IPCS_RATE_FAST: s->poll_priority = QB_LOOP_HIGH; break; case QB_IPCS_RATE_SLOW: case QB_IPCS_RATE_OFF: case QB_IPCS_RATE_OFF_2: s->poll_priority = QB_LOOP_LOW; break; default: case QB_IPCS_RATE_NORMAL: s->poll_priority = QB_LOOP_MED; break; } - for (pos = s->connections.next, n = pos->next; - pos != &s->connections; pos = n, n = pos->next) { + qb_list_for_each_safe(pos, n, &s->connections) { c = qb_list_entry(pos, struct qb_ipcs_connection, list); qb_ipcs_connection_ref(c); if (rl == QB_IPCS_RATE_OFF) { qb_ipcs_flowcontrol_set(c, 1); } else if (rl == QB_IPCS_RATE_OFF_2) { qb_ipcs_flowcontrol_set(c, 2); } else { qb_ipcs_flowcontrol_set(c, QB_FALSE); } if (old_p != s->poll_priority) { (void)_modify_dispatch_descriptor_(c); } qb_ipcs_connection_unref(c); } } void qb_ipcs_ref(struct qb_ipcs_service *s) { qb_atomic_int_inc(&s->ref_count); } void qb_ipcs_unref(struct qb_ipcs_service *s) { int32_t free_it; struct qb_ipcs_connection *c = NULL; struct qb_list_head *pos; struct qb_list_head *n; assert(s->ref_count > 0); free_it = qb_atomic_int_dec_and_test(&s->ref_count); if (free_it) { qb_util_log(LOG_DEBUG, "%s() - destroying", __func__); - for (pos = s->connections.next, n = pos->next; - pos != &s->connections; pos = n, n = pos->next) { + qb_list_for_each_safe(pos, n, &s->connections) { c = qb_list_entry(pos, struct qb_ipcs_connection, list); if (c == NULL) { continue; } qb_ipcs_disconnect(c); } (void)qb_ipcs_us_withdraw(s); free(s); } } void qb_ipcs_destroy(struct qb_ipcs_service *s) { qb_ipcs_unref(s); } /* * connection API */ static struct qb_ipc_one_way * _event_sock_one_way_get(struct qb_ipcs_connection * c) { if (c->service->needs_sock_for_poll) { return &c->setup; } if (c->event.type == QB_IPC_SOCKET) { return &c->event; } return NULL; } static struct qb_ipc_one_way * _response_sock_one_way_get(struct qb_ipcs_connection * c) { if (c->service->needs_sock_for_poll) { return &c->setup; } if (c->response.type == QB_IPC_SOCKET) { return &c->response; } return NULL; } ssize_t qb_ipcs_response_send(struct qb_ipcs_connection *c, const void *data, size_t size) { ssize_t res; if (c == NULL) { return -EINVAL; } qb_ipcs_connection_ref(c); res = c->service->funcs.send(&c->response, data, size); if (res == size) { c->stats.responses++; } else if (res == -EAGAIN || res == -ETIMEDOUT) { struct qb_ipc_one_way *ow = _response_sock_one_way_get(c); if (ow) { ssize_t res2 = qb_ipc_us_ready(ow, 0, POLLOUT); if (res2 < 0) { res = res2; } } c->stats.send_retries++; } qb_ipcs_connection_unref(c); return res; } ssize_t qb_ipcs_response_sendv(struct qb_ipcs_connection * c, const struct iovec * iov, size_t iov_len) { ssize_t res; if (c == NULL) { return -EINVAL; } qb_ipcs_connection_ref(c); res = c->service->funcs.sendv(&c->response, iov, iov_len); if (res > 0) { c->stats.responses++; } else if (res == -EAGAIN || res == -ETIMEDOUT) { struct qb_ipc_one_way *ow = _response_sock_one_way_get(c); if (ow) { ssize_t res2 = qb_ipc_us_ready(ow, 0, POLLOUT); if (res2 < 0) { res = res2; } } c->stats.send_retries++; } qb_ipcs_connection_unref(c); return res; } static int32_t resend_event_notifications(struct qb_ipcs_connection *c) { ssize_t res = 0; if (c->outstanding_notifiers > 0) { res = qb_ipc_us_send(&c->setup, c->receive_buf, c->outstanding_notifiers); } if (res > 0) { c->outstanding_notifiers -= res; } assert(c->outstanding_notifiers >= 0); if (c->outstanding_notifiers == 0) { c->poll_events = POLLIN | POLLPRI | POLLNVAL; (void)_modify_dispatch_descriptor_(c); } return res; } static int32_t new_event_notification(struct qb_ipcs_connection * c) { ssize_t res = 0; if (!c->service->needs_sock_for_poll) { return res; } assert(c->outstanding_notifiers >= 0); if (c->outstanding_notifiers > 0) { c->outstanding_notifiers++; } else { res = qb_ipc_us_send(&c->setup, &c->outstanding_notifiers, 1); if (res == -EAGAIN) { /* * notify the client later, when we can. */ c->outstanding_notifiers++; c->poll_events = POLLOUT | POLLIN | POLLPRI | POLLNVAL; (void)_modify_dispatch_descriptor_(c); } } return res; } ssize_t qb_ipcs_event_send(struct qb_ipcs_connection * c, const void *data, size_t size) { ssize_t res; ssize_t resn; if (c == NULL) { return -EINVAL; } qb_ipcs_connection_ref(c); res = c->service->funcs.send(&c->event, data, size); if (res == size) { c->stats.events++; resn = new_event_notification(c); if (resn < 0 && resn != -EAGAIN) { errno = -resn; qb_util_perror(LOG_WARNING, "new_event_notification (%s)", c->description); res = resn; } } else if (res == -EAGAIN || res == -ETIMEDOUT) { struct qb_ipc_one_way *ow = _event_sock_one_way_get(c); if (ow) { resn = qb_ipc_us_ready(ow, 0, POLLOUT); if (resn < 0) { res = resn; } } c->stats.send_retries++; } qb_ipcs_connection_unref(c); return res; } ssize_t qb_ipcs_event_sendv(struct qb_ipcs_connection * c, const struct iovec * iov, size_t iov_len) { ssize_t res; ssize_t resn; if (c == NULL) { return -EINVAL; } qb_ipcs_connection_ref(c); res = c->service->funcs.sendv(&c->event, iov, iov_len); if (res > 0) { c->stats.events++; resn = new_event_notification(c); if (resn < 0 && resn != -EAGAIN) { errno = -resn; qb_util_perror(LOG_WARNING, "new_event_notification (%s)", c->description); res = resn; } } else if (res == -EAGAIN || res == -ETIMEDOUT) { struct qb_ipc_one_way *ow = _event_sock_one_way_get(c); if (ow) { resn = qb_ipc_us_ready(ow, 0, POLLOUT); if (resn < 0) { res = resn; } } c->stats.send_retries++; } qb_ipcs_connection_unref(c); return res; } qb_ipcs_connection_t * qb_ipcs_connection_first_get(struct qb_ipcs_service * s) { struct qb_ipcs_connection *c; - struct qb_list_head *iter; if (qb_list_empty(&s->connections)) { return NULL; } - iter = s->connections.next; - c = qb_list_entry(iter, struct qb_ipcs_connection, list); + c = qb_list_first_entry(&s->connections, struct qb_ipcs_connection, list); qb_ipcs_connection_ref(c); return c; } qb_ipcs_connection_t * qb_ipcs_connection_next_get(struct qb_ipcs_service * s, struct qb_ipcs_connection * current) { struct qb_ipcs_connection *c; - struct qb_list_head *iter; - if (current == NULL || current->list.next == &s->connections) { + if (current == NULL || + qb_list_is_last(¤t->list, &s->connections)) { return NULL; } - iter = current->list.next; - c = qb_list_entry(iter, struct qb_ipcs_connection, list); + c = qb_list_first_entry(¤t->list, struct qb_ipcs_connection, list); qb_ipcs_connection_ref(c); return c; } int32_t qb_ipcs_service_id_get(struct qb_ipcs_connection * c) { if (c == NULL) { return -EINVAL; } return c->service->service_id; } struct qb_ipcs_connection * qb_ipcs_connection_alloc(struct qb_ipcs_service *s) { struct qb_ipcs_connection *c = calloc(1, sizeof(struct qb_ipcs_connection)); if (c == NULL) { return NULL; } c->refcount = 1; c->service = s; c->pid = 0; c->euid = -1; c->egid = -1; qb_list_init(&c->list); c->receive_buf = NULL; c->context = NULL; c->fc_enabled = QB_FALSE; c->state = QB_IPCS_CONNECTION_INACTIVE; c->poll_events = POLLIN | POLLPRI | POLLNVAL; c->setup.type = s->type; c->request.type = s->type; c->response.type = s->type; c->event.type = s->type; (void)strlcpy(c->description, "not set yet", CONNECTION_DESCRIPTION); return c; } void qb_ipcs_connection_ref(struct qb_ipcs_connection *c) { if (c) { qb_atomic_int_inc(&c->refcount); } } void qb_ipcs_connection_unref(struct qb_ipcs_connection *c) { int32_t free_it; if (c == NULL) { return; } if (c->refcount < 1) { qb_util_log(LOG_ERR, "ref:%d state:%d (%s)", c->refcount, c->state, c->description); assert(0); } free_it = qb_atomic_int_dec_and_test(&c->refcount); if (free_it) { qb_list_del(&c->list); if (c->service->serv_fns.connection_destroyed) { c->service->serv_fns.connection_destroyed(c); } c->service->funcs.disconnect(c); free(c->receive_buf); free(c); } } void qb_ipcs_disconnect(struct qb_ipcs_connection *c) { int32_t res = 0; qb_loop_job_dispatch_fn rerun_job; if (c == NULL) { return; } qb_util_log(LOG_DEBUG, "%s(%s) state:%d", __func__, c->description, c->state); if (c->state == QB_IPCS_CONNECTION_ACTIVE) { c->state = QB_IPCS_CONNECTION_INACTIVE; c->service->stats.closed_connections++; qb_ipcs_sockets_disconnect(c); /* return early as it's an incomplete connection. */ return; } if (c->state == QB_IPCS_CONNECTION_ESTABLISHED) { c->state = QB_IPCS_CONNECTION_SHUTTING_DOWN; c->service->stats.active_connections--; c->service->stats.closed_connections++; qb_ipcs_sockets_disconnect(c); } if (c->state == QB_IPCS_CONNECTION_SHUTTING_DOWN) { res = 0; if (c->service->serv_fns.connection_closed) { res = c->service->serv_fns.connection_closed(c); } if (res == 0) { qb_ipcs_connection_unref(c); } else { /* OK, so they want the connection_closed * function re-run */ rerun_job = (qb_loop_job_dispatch_fn) qb_ipcs_disconnect; res = c->service->poll_fns.job_add(QB_LOOP_LOW, c, rerun_job); if (res != 0) { /* last ditch attempt to cleanup */ qb_ipcs_connection_unref(c); } } } } static void qb_ipcs_flowcontrol_set(struct qb_ipcs_connection *c, int32_t fc_enable) { if (c == NULL) { return; } if (c->fc_enabled != fc_enable) { c->service->funcs.fc_set(&c->request, fc_enable); c->fc_enabled = fc_enable; c->stats.flow_control_state = fc_enable; c->stats.flow_control_count++; } } static int32_t _process_request_(struct qb_ipcs_connection *c, int32_t ms_timeout) { int32_t res = 0; ssize_t size; struct qb_ipc_request_header *hdr; qb_ipcs_connection_ref(c); if (c->service->funcs.peek && c->service->funcs.reclaim) { size = c->service->funcs.peek(&c->request, (void **)&hdr, ms_timeout); } else { hdr = c->receive_buf; size = c->service->funcs.recv(&c->request, hdr, c->request.max_msg_size, ms_timeout); } if (size < 0) { if (size != -EAGAIN && size != -ETIMEDOUT) { qb_util_perror(LOG_DEBUG, "recv from client connection failed (%s)", c->description); } else { c->stats.recv_retries++; } res = size; goto cleanup; } else if (size == 0 || hdr->id == QB_IPC_MSG_DISCONNECT) { qb_util_log(LOG_DEBUG, "client requesting a disconnect (%s)", c->description); qb_ipcs_disconnect(c); c = NULL; res = -ESHUTDOWN; } else { c->stats.requests++; res = c->service->serv_fns.msg_process(c, hdr, hdr->size); /* 0 == good, negative == backoff */ if (res < 0) { res = -ENOBUFS; } else { res = size; } } if (c && c->service->funcs.peek && c->service->funcs.reclaim) { c->service->funcs.reclaim(&c->request); } cleanup: qb_ipcs_connection_unref(c); return res; } #define IPC_REQUEST_TIMEOUT 10 #define MAX_RECV_MSGS 50 int32_t qb_ipcs_dispatch_service_request(int32_t fd, int32_t revents, void *data) { int32_t res = _process_request_((struct qb_ipcs_connection *)data, IPC_REQUEST_TIMEOUT); if (res > 0) { return 0; } return res; } static ssize_t _request_q_len_get(struct qb_ipcs_connection *c) { ssize_t q_len; if (c->service->funcs.q_len_get) { q_len = c->service->funcs.q_len_get(&c->request); if (q_len <= 0) { return q_len; } if (c->service->poll_priority == QB_LOOP_MED) { q_len = QB_MIN(q_len, 5); } else if (c->service->poll_priority == QB_LOOP_LOW) { q_len = 1; } else { q_len = QB_MIN(q_len, MAX_RECV_MSGS); } } else { q_len = 1; } return q_len; } int32_t qb_ipcs_dispatch_connection_request(int32_t fd, int32_t revents, void *data) { struct qb_ipcs_connection *c = (struct qb_ipcs_connection *)data; char bytes[MAX_RECV_MSGS]; int32_t res; int32_t res2; int32_t recvd = 0; ssize_t avail; if (revents & POLLNVAL) { qb_util_log(LOG_DEBUG, "NVAL conn (%s)", c->description); return -EINVAL; } if (revents & POLLHUP) { qb_util_log(LOG_DEBUG, "HUP conn (%s)", c->description); qb_ipcs_disconnect(c); return -ESHUTDOWN; } if (revents & POLLOUT) { res = resend_event_notifications(c); if (res < 0 && res != -EAGAIN) { errno = -res; qb_util_perror(LOG_WARNING, "resend_event_notifications (%s)", c->description); } if ((revents & POLLIN) == 0) { return 0; } } if (c->fc_enabled) { return 0; } avail = _request_q_len_get(c); if (c->service->needs_sock_for_poll && avail == 0) { res2 = qb_ipc_us_recv(&c->setup, bytes, 1, 0); if (qb_ipc_us_sock_error_is_disconnected(res2)) { errno = -res2; qb_util_perror(LOG_WARNING, "conn (%s) disconnected", c->description); qb_ipcs_disconnect(c); return -ESHUTDOWN; } else { qb_util_log(LOG_WARNING, "conn (%s) Nothing in q but got POLLIN on fd:%d (res2:%d)", c->description, fd, res2); return 0; } } do { res = _process_request_(c, IPC_REQUEST_TIMEOUT); if (res > 0 || res == -ENOBUFS || res == -EINVAL) { recvd++; } if (res > 0) { avail--; } } while (avail > 0 && res > 0 && !c->fc_enabled); if (c->service->needs_sock_for_poll && recvd > 0) { res2 = qb_ipc_us_recv(&c->setup, bytes, recvd, -1); if (res2 < 0) { errno = -res2; qb_util_perror(LOG_ERR, "error receiving from setup sock (%s)", c->description); } } res = QB_MIN(0, res); if (res == -EAGAIN || res == -ETIMEDOUT || res == -ENOBUFS) { res = 0; } if (res != 0) { if (res != -ENOTCONN) { /* * Abnormal state (ENOTCONN is normal shutdown). */ errno = -res; qb_util_perror(LOG_ERR, "request returned error (%s)", c->description); } qb_ipcs_connection_unref(c); } return res; } void qb_ipcs_context_set(struct qb_ipcs_connection *c, void *context) { if (c == NULL) { return; } c->context = context; } void * qb_ipcs_context_get(struct qb_ipcs_connection *c) { if (c == NULL) { return NULL; } return c->context; } int32_t qb_ipcs_connection_stats_get(qb_ipcs_connection_t * c, struct qb_ipcs_connection_stats * stats, int32_t clear_after_read) { if (c == NULL) { return -EINVAL; } memcpy(stats, &c->stats, sizeof(struct qb_ipcs_connection_stats)); if (clear_after_read) { memset(&c->stats, 0, sizeof(struct qb_ipcs_connection_stats_2)); c->stats.client_pid = c->pid; } return 0; } struct qb_ipcs_connection_stats_2* qb_ipcs_connection_stats_get_2(qb_ipcs_connection_t *c, int32_t clear_after_read) { struct qb_ipcs_connection_stats_2* stats; if (c == NULL) { errno = EINVAL; return NULL; } stats = calloc(1, sizeof(struct qb_ipcs_connection_stats_2)); if (stats == NULL) { return NULL; } memcpy(stats, &c->stats, sizeof(struct qb_ipcs_connection_stats_2)); if (c->service->funcs.q_len_get) { stats->event_q_length = c->service->funcs.q_len_get(&c->event); } else { stats->event_q_length = 0; } if (clear_after_read) { memset(&c->stats, 0, sizeof(struct qb_ipcs_connection_stats_2)); c->stats.client_pid = c->pid; } return stats; } int32_t qb_ipcs_stats_get(struct qb_ipcs_service * s, struct qb_ipcs_stats * stats, int32_t clear_after_read) { if (s == NULL) { return -EINVAL; } memcpy(stats, &s->stats, sizeof(struct qb_ipcs_stats)); if (clear_after_read) { memset(&s->stats, 0, sizeof(struct qb_ipcs_stats)); } return 0; } void qb_ipcs_connection_auth_set(qb_ipcs_connection_t *c, uid_t uid, gid_t gid, mode_t mode) { if (c) { c->auth.uid = uid; c->auth.gid = gid; c->auth.mode = mode; } } diff --git a/lib/log.c b/lib/log.c index 9c3504b..925dae8 100644 --- a/lib/log.c +++ b/lib/log.c @@ -1,1010 +1,1010 @@ /* * Copyright (C) 2011 Red Hat, Inc. * * All rights reserved. * * Author: Angus Salkeld * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include #ifdef HAVE_LINK_H #include #endif /* HAVE_LINK_H */ #include #include #ifdef HAVE_DLFCN_H #include #endif /* HAVE_DLFCN_H */ #include #include #include #include #include #include #include "log_int.h" #include "util_int.h" static struct qb_log_target conf[QB_LOG_TARGET_MAX]; static uint32_t conf_active_max = 0; static int32_t in_logger = QB_FALSE; static int32_t logger_inited = QB_FALSE; static pthread_rwlock_t _listlock; static qb_log_filter_fn _custom_filter_fn = NULL; static QB_LIST_DECLARE(tags_head); static QB_LIST_DECLARE(callsite_sections); struct callsite_section { struct qb_log_callsite *start; struct qb_log_callsite *stop; struct qb_list_head list; }; static int32_t _log_target_enable(struct qb_log_target *t); static void _log_target_disable(struct qb_log_target *t); static void _log_filter_apply(struct callsite_section *sect, uint32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority); static void _log_filter_apply_to_cs(struct qb_log_callsite *cs, uint32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority); /* deprecated method of getting internal log messages */ static qb_util_log_fn_t old_internal_log_fn = NULL; void qb_util_set_log_function(qb_util_log_fn_t fn) { old_internal_log_fn = fn; } static int32_t _cs_matches_filter_(struct qb_log_callsite *cs, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority) { int32_t match = QB_FALSE; if (cs->priority > low_priority || cs->priority < high_priority) { return QB_FALSE; } if (strcmp(text, "*") == 0) { return QB_TRUE; } if (type == QB_LOG_FILTER_FILE || type == QB_LOG_FILTER_FUNCTION) { char token[500]; const char *offset = NULL; const char *next = text; do { offset = next; next = strchrnul(offset, ','); snprintf(token, 499, "%.*s", (int)(next - offset), offset); if (type == QB_LOG_FILTER_FILE) { match = (strstr(cs->filename, token) != NULL); } else { match = (strstr(cs->function, token) != NULL); } if (!match && next[0] != 0) { next++; } } while (match == QB_FALSE && next != NULL && next[0] != 0); } else if (type == QB_LOG_FILTER_FORMAT) { if (strstr(cs->format, text)) { match = QB_TRUE; } } return match; } void qb_log_real_va_(struct qb_log_callsite *cs, va_list ap) { int32_t found_threaded; struct qb_log_target *t; struct timespec tv; int32_t pos; int len; int32_t formatted = QB_FALSE; char buf[QB_LOG_MAX_LEN]; char *str = buf; va_list ap_copy; if (in_logger || cs == NULL) { return; } in_logger = QB_TRUE; if (old_internal_log_fn) { if (qb_bit_is_set(cs->tags, QB_LOG_TAG_LIBQB_MSG_BIT)) { if (!formatted) { va_copy(ap_copy, ap); len = vsnprintf(str, QB_LOG_MAX_LEN, cs->format, ap_copy); va_end(ap_copy); if (str[len - 1] == '\n') str[len - 1] = '\0'; formatted = QB_TRUE; } old_internal_log_fn(cs->filename, cs->lineno, cs->priority, str); } } qb_util_timespec_from_epoch_get(&tv); /* * 1 if we can find a threaded target that needs this log then post it * 2 foreach non-threaded target call it's logger function */ found_threaded = QB_FALSE; for (pos = 0; pos <= conf_active_max; pos++) { t = &conf[pos]; if (t->state != QB_LOG_STATE_ENABLED) { continue; } if (t->threaded) { if (!found_threaded && qb_bit_is_set(cs->targets, t->pos)) { found_threaded = QB_TRUE; if (!formatted) { va_copy(ap_copy, ap); len = vsnprintf(str, QB_LOG_MAX_LEN, cs->format, ap_copy); va_end(ap_copy); if (str[len - 1] == '\n') str[len - 1] = '\0'; formatted = QB_TRUE; } } } else { if (qb_bit_is_set(cs->targets, t->pos)) { if (t->vlogger) { va_copy(ap_copy, ap); t->vlogger(t->pos, cs, tv.tv_sec, ap_copy); va_end(ap_copy); } else if (t->logger) { if (!formatted) { va_copy(ap_copy, ap); len = vsnprintf(str, QB_LOG_MAX_LEN, cs->format, ap_copy); va_end(ap_copy); if (str[len - 1] == '\n') str[len - 1] = '\0'; formatted = QB_TRUE; } t->logger(t->pos, cs, tv.tv_sec, str); } } } } if (found_threaded) { qb_log_thread_log_post(cs, tv.tv_sec, str); } in_logger = QB_FALSE; } void qb_log_real_(struct qb_log_callsite *cs, ...) { va_list ap; va_start(ap, cs); qb_log_real_va_(cs, ap); va_end(ap); } void qb_log_thread_log_write(struct qb_log_callsite *cs, time_t timestamp, const char *buffer) { struct qb_log_target *t; int32_t pos; for (pos = 0; pos <= conf_active_max; pos++) { t = &conf[pos]; if (t->state != QB_LOG_STATE_ENABLED) { continue; } if (!t->threaded) { continue; } if (qb_bit_is_set(cs->targets, t->pos)) { t->logger(t->pos, cs, timestamp, buffer); } } } struct qb_log_callsite* qb_log_callsite_get(const char *function, const char *filename, const char *format, uint8_t priority, uint32_t lineno, uint32_t tags) { struct qb_log_target *t; struct qb_log_filter *flt; struct qb_log_callsite *cs; int32_t new_dcs = QB_FALSE; struct qb_list_head *f_item; int32_t pos; if (!logger_inited) { return NULL; } cs = qb_log_dcs_get(&new_dcs, function, filename, format, priority, lineno, tags); if (cs == NULL) { return NULL; } if (new_dcs) { pthread_rwlock_rdlock(&_listlock); for (pos = 0; pos <= conf_active_max; pos++) { t = &conf[pos]; if (t->state != QB_LOG_STATE_ENABLED) { continue; } - for (f_item = t->filter_head.next; f_item != &t->filter_head; f_item = f_item->next) { + qb_list_for_each(f_item, &t->filter_head) { flt = qb_list_entry(f_item, struct qb_log_filter, list); _log_filter_apply_to_cs(cs, t->pos, flt->conf, flt->type, flt->text, flt->high_priority, flt->low_priority); } } if (tags == 0) { - for (f_item = tags_head.next; f_item != &tags_head; f_item = f_item->next) { + qb_list_for_each(f_item, &tags_head) { flt = qb_list_entry(f_item, struct qb_log_filter, list); _log_filter_apply_to_cs(cs, flt->new_value, flt->conf, flt->type, flt->text, flt->high_priority, flt->low_priority); } } else { cs->tags = tags; } if (_custom_filter_fn) { _custom_filter_fn(cs); } pthread_rwlock_unlock(&_listlock); } else if (cs->tags != tags) { cs->tags = tags; if (_custom_filter_fn) { _custom_filter_fn(cs); } } return cs; } void qb_log_from_external_source_va(const char *function, const char *filename, const char *format, uint8_t priority, uint32_t lineno, uint32_t tags, va_list ap) { struct qb_log_callsite *cs; if (!logger_inited) { return; } cs = qb_log_callsite_get(function, filename, format, priority, lineno, tags); qb_log_real_va_(cs, ap); } void qb_log_from_external_source(const char *function, const char *filename, const char *format, uint8_t priority, uint32_t lineno, uint32_t tags, ...) { struct qb_log_callsite *cs; va_list ap; if (!logger_inited) { return; } cs = qb_log_callsite_get(function, filename, format, priority, lineno, tags); va_start(ap, tags); qb_log_real_va_(cs, ap); va_end(ap); } int32_t qb_log_callsites_register(struct qb_log_callsite *_start, struct qb_log_callsite *_stop) { struct callsite_section *sect; struct qb_log_callsite *cs; struct qb_log_target *t; struct qb_log_filter *flt; int32_t pos; if (_start == NULL || _stop == NULL) { return -EINVAL; } pthread_rwlock_rdlock(&_listlock); qb_list_for_each_entry(sect, &callsite_sections, list) { if (sect->start == _start || sect->stop == _stop) { pthread_rwlock_unlock(&_listlock); return -EEXIST; } } pthread_rwlock_unlock(&_listlock); sect = calloc(1, sizeof(struct callsite_section)); if (sect == NULL) { return -ENOMEM; } sect->start = _start; sect->stop = _stop; qb_list_init(§->list); pthread_rwlock_wrlock(&_listlock); qb_list_add(§->list, &callsite_sections); /* * Now apply the filters on these new callsites */ for (pos = 0; pos <= conf_active_max; pos++) { t = &conf[pos]; if (t->state != QB_LOG_STATE_ENABLED) { continue; } qb_list_for_each_entry(flt, &t->filter_head, list) { _log_filter_apply(sect, t->pos, flt->conf, flt->type, flt->text, flt->high_priority, flt->low_priority); } } qb_list_for_each_entry(flt, &tags_head, list) { _log_filter_apply(sect, flt->new_value, flt->conf, flt->type, flt->text, flt->high_priority, flt->low_priority); } pthread_rwlock_unlock(&_listlock); if (_custom_filter_fn) { for (cs = sect->start; cs < sect->stop; cs++) { if (cs->lineno > 0) { _custom_filter_fn(cs); } } } /* qb_log_callsites_dump_sect(sect); */ return 0; } static void qb_log_callsites_dump_sect(struct callsite_section *sect) { struct qb_log_callsite *cs; printf(" start %p - stop %p\n", sect->start, sect->stop); printf("filename lineno targets tags\n"); for (cs = sect->start; cs < sect->stop; cs++) { if (cs->lineno > 0) { printf("%12s %6d %16d %16d\n", cs->filename, cs->lineno, cs->targets, cs->tags); } } } void qb_log_callsites_dump(void) { struct callsite_section *sect; int32_t l; pthread_rwlock_rdlock(&_listlock); l = qb_list_length(&callsite_sections); printf("Callsite Database [%d]\n", l); printf("---------------------\n"); qb_list_for_each_entry(sect, &callsite_sections, list) { qb_log_callsites_dump_sect(sect); } pthread_rwlock_unlock(&_listlock); } static int32_t _log_filter_exists(struct qb_list_head *list_head, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority, uint32_t new_value) { struct qb_log_filter *flt; qb_list_for_each_entry(flt, list_head, list) { if (flt->type == type && flt->high_priority == high_priority && flt->low_priority == low_priority && flt->new_value == new_value && strcmp(flt->text, text) == 0) { return QB_TRUE; } } return QB_FALSE; } static int32_t _log_filter_store(uint32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority) { struct qb_log_filter *flt; struct qb_list_head *iter; struct qb_list_head *next; struct qb_list_head *list_head; switch (c) { case QB_LOG_FILTER_ADD: case QB_LOG_FILTER_REMOVE: case QB_LOG_FILTER_CLEAR_ALL: list_head = &conf[t].filter_head; break; case QB_LOG_TAG_SET: case QB_LOG_TAG_CLEAR: case QB_LOG_TAG_CLEAR_ALL: list_head = &tags_head; break; default: return -ENOSYS; } if (c == QB_LOG_FILTER_ADD || c == QB_LOG_TAG_SET) { if (text == NULL) { return -EINVAL; } if (_log_filter_exists(list_head, type, text, high_priority, low_priority, t)) { return -EEXIST; } flt = calloc(1, sizeof(struct qb_log_filter)); if (flt == NULL) { return -ENOMEM; } qb_list_init(&flt->list); flt->conf = c; flt->type = type; flt->text = strdup(text); if (flt->text == NULL) { free(flt); return -ENOMEM; } flt->high_priority = high_priority; flt->low_priority = low_priority; flt->new_value = t; qb_list_add_tail(&flt->list, list_head); } else if (c == QB_LOG_FILTER_REMOVE || c == QB_LOG_TAG_CLEAR) { qb_list_for_each_safe(iter, next, list_head) { flt = qb_list_entry(iter, struct qb_log_filter, list); if (flt->type == type && flt->low_priority <= low_priority && flt->high_priority >= high_priority && (strcmp(flt->text, text) == 0 || strcmp("*", text) == 0)) { qb_list_del(iter); free(flt->text); free(flt); return 0; } } } else if (c == QB_LOG_FILTER_CLEAR_ALL || c == QB_LOG_TAG_CLEAR_ALL) { qb_list_for_each_safe(iter, next, list_head) { flt = qb_list_entry(iter, struct qb_log_filter, list); qb_list_del(iter); free(flt->text); free(flt); } } return 0; } static void _log_filter_apply(struct callsite_section *sect, uint32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority) { struct qb_log_callsite *cs; for (cs = sect->start; cs < sect->stop; cs++) { if (cs->lineno > 0) { _log_filter_apply_to_cs(cs, t, c, type, text, high_priority, low_priority); } } } /* #define _QB_FILTER_DEBUGGING_ 1 */ static void _log_filter_apply_to_cs(struct qb_log_callsite *cs, uint32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t high_priority, uint8_t low_priority) { if (c == QB_LOG_FILTER_CLEAR_ALL) { qb_bit_clear(cs->targets, t); return; } else if (c == QB_LOG_TAG_CLEAR_ALL) { cs->tags = 0; return; } if (_cs_matches_filter_(cs, type, text, high_priority, low_priority)) { #ifdef _QB_FILTER_DEBUGGING_ uint32_t old_targets = cs->targets; uint32_t old_tags = cs->tags; #endif /* _QB_FILTER_DEBUGGING_ */ if (c == QB_LOG_FILTER_ADD) { qb_bit_set(cs->targets, t); } else if (c == QB_LOG_FILTER_REMOVE) { qb_bit_clear(cs->targets, t); } else if (c == QB_LOG_TAG_SET) { cs->tags = t; } else if (c == QB_LOG_TAG_CLEAR) { cs->tags = 0; } #ifdef _QB_FILTER_DEBUGGING_ if (old_targets != cs->targets) { printf("targets: %s:%u value(%d) %d -> %d\n", cs->filename, cs->lineno, t, old_targets, cs->targets); } if (old_tags != cs->tags) { printf("tags: %s:%u value(%d) %d -> %d\n", cs->filename, cs->lineno, t, old_tags, cs->tags); } #endif /* _QB_FILTER_DEBUGGING_ */ } } int32_t qb_log_filter_ctl2(int32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char * text, uint8_t high_priority, uint8_t low_priority) { struct callsite_section *sect; int32_t rc; if (!logger_inited) { return -EINVAL; } if (c == QB_LOG_FILTER_ADD || c == QB_LOG_FILTER_CLEAR_ALL || c == QB_LOG_FILTER_REMOVE) { if (t < 0 || t >= QB_LOG_TARGET_MAX || conf[t].state == QB_LOG_STATE_UNUSED) { return -EBADF; } } if (text == NULL || low_priority < high_priority || type > QB_LOG_FILTER_FORMAT || c > QB_LOG_TAG_CLEAR_ALL) { return -EINVAL; } pthread_rwlock_rdlock(&_listlock); rc = _log_filter_store(t, c, type, text, high_priority, low_priority); if (rc < 0) { pthread_rwlock_unlock(&_listlock); return rc; } qb_list_for_each_entry(sect, &callsite_sections, list) { _log_filter_apply(sect, t, c, type, text, high_priority, low_priority); } pthread_rwlock_unlock(&_listlock); return 0; } int32_t qb_log_filter_fn_set(qb_log_filter_fn fn) { struct callsite_section *sect; struct qb_log_callsite *cs; if (!logger_inited) { return -EINVAL; } _custom_filter_fn = fn; if (_custom_filter_fn == NULL) { return 0; } qb_list_for_each_entry(sect, &callsite_sections, list) { for (cs = sect->start; cs < sect->stop; cs++) { if (cs->lineno > 0) { _custom_filter_fn(cs); } } } return 0; } int32_t qb_log_filter_ctl(int32_t t, enum qb_log_filter_conf c, enum qb_log_filter_type type, const char *text, uint8_t priority) { return qb_log_filter_ctl2(t, c, type, text, LOG_EMERG, priority); } #ifdef QB_HAVE_ATTRIBUTE_SECTION static int32_t _log_so_walk_callback(struct dl_phdr_info *info, size_t size, void *data) { if (strlen(info->dlpi_name) > 0) { void *handle; void *start; void *stop; const char *error; handle = dlopen(info->dlpi_name, RTLD_LAZY); error = dlerror(); if (!handle || error) { qb_log(LOG_ERR, "%s", error); if (handle) { dlclose(handle); } return 0; } start = dlsym(handle, "__start___verbose"); error = dlerror(); if (error) { goto done; } stop = dlsym(handle, "__stop___verbose"); error = dlerror(); if (error) { goto done; } else { qb_log_callsites_register(start, stop); } done: dlclose(handle); } return 0; } #endif /* QB_HAVE_ATTRIBUTE_SECTION */ static void _log_target_state_set(struct qb_log_target *t, enum qb_log_target_state s) { int32_t i; int32_t a_set = QB_FALSE; int32_t u_set = QB_FALSE; t->state = s; for (i = 31; i >= 0; i--) { if (!a_set && conf[i].state == QB_LOG_STATE_ENABLED) { a_set = QB_TRUE; conf_active_max = i; } if (!u_set && conf[i].state != QB_LOG_STATE_UNUSED) { u_set = QB_TRUE; } } } void qb_log_init(const char *name, int32_t facility, uint8_t priority) { int32_t i; i = pthread_rwlock_init(&_listlock, NULL); assert(i == 0); qb_log_format_init(); for (i = 0; i < QB_LOG_TARGET_MAX; i++) { conf[i].pos = i; conf[i].debug = QB_FALSE; conf[i].file_sync = QB_FALSE; conf[i].state = QB_LOG_STATE_UNUSED; (void)strlcpy(conf[i].name, name, PATH_MAX); conf[i].facility = facility; qb_list_init(&conf[i].filter_head); } qb_log_dcs_init(); #ifdef QB_HAVE_ATTRIBUTE_SECTION qb_log_callsites_register(__start___verbose, __stop___verbose); dl_iterate_phdr(_log_so_walk_callback, NULL); #endif /* QB_HAVE_ATTRIBUTE_SECTION */ conf[QB_LOG_STDERR].state = QB_LOG_STATE_DISABLED; conf[QB_LOG_BLACKBOX].state = QB_LOG_STATE_DISABLED; conf[QB_LOG_STDOUT].state = QB_LOG_STATE_DISABLED; logger_inited = QB_TRUE; (void)qb_log_syslog_open(&conf[QB_LOG_SYSLOG]); _log_target_state_set(&conf[QB_LOG_SYSLOG], QB_LOG_STATE_ENABLED); (void)qb_log_filter_ctl(QB_LOG_SYSLOG, QB_LOG_FILTER_ADD, QB_LOG_FILTER_FILE, "*", priority); } void qb_log_fini(void) { struct qb_log_target *t; struct qb_log_filter *flt; struct callsite_section *s; struct qb_list_head *iter; struct qb_list_head *iter2; struct qb_list_head *next; struct qb_list_head *next2; int32_t pos; if (!logger_inited) { return; } logger_inited = QB_FALSE; qb_log_thread_stop(); pthread_rwlock_destroy(&_listlock); for (pos = 0; pos <= conf_active_max; pos++) { t = &conf[pos]; _log_target_disable(t); qb_list_for_each_safe(iter2, next2, &t->filter_head) { flt = qb_list_entry(iter2, struct qb_log_filter, list); qb_list_del(iter2); free(flt->text); free(flt); } } qb_log_format_fini(); qb_log_dcs_fini(); qb_list_for_each_safe(iter, next, &callsite_sections) { s = qb_list_entry(iter, struct callsite_section, list); qb_list_del(iter); free(s); } qb_list_for_each_safe(iter, next, &tags_head) { flt = qb_list_entry(iter, struct qb_log_filter, list); qb_list_del(iter); free(flt->text); free(flt); } } struct qb_log_target * qb_log_target_alloc(void) { int32_t i; for (i = 0; i < QB_LOG_TARGET_MAX; i++) { if (conf[i].state == QB_LOG_STATE_UNUSED) { _log_target_state_set(&conf[i], QB_LOG_STATE_DISABLED); return &conf[i]; } } return NULL; } void qb_log_target_free(struct qb_log_target *t) { (void)qb_log_filter_ctl(t->pos, QB_LOG_FILTER_CLEAR_ALL, QB_LOG_FILTER_FILE, NULL, 0); t->debug = QB_FALSE; t->filename[0] = '\0'; qb_log_format_set(t->pos, NULL); _log_target_state_set(t, QB_LOG_STATE_UNUSED); } struct qb_log_target * qb_log_target_get(int32_t pos) { return &conf[pos]; } void * qb_log_target_user_data_get(int32_t t) { if (t < 0 || t >= QB_LOG_TARGET_MAX || conf[t].state == QB_LOG_STATE_UNUSED) { errno = -EBADF; return NULL; } return conf[t].instance; } int32_t qb_log_target_user_data_set(int32_t t, void *user_data) { if (!logger_inited) { return -EINVAL; } if (t < 0 || t >= QB_LOG_TARGET_MAX || conf[t].state == QB_LOG_STATE_UNUSED) { return -EBADF; } conf[t].instance = user_data; return 0; } int32_t qb_log_custom_open(qb_log_logger_fn log_fn, qb_log_close_fn close_fn, qb_log_reload_fn reload_fn, void *user_data) { struct qb_log_target *t; t = qb_log_target_alloc(); if (t == NULL) { return -errno; } t->instance = user_data; snprintf(t->filename, PATH_MAX, "custom-%d", t->pos); t->logger = log_fn; t->vlogger = NULL; t->reload = reload_fn; t->close = close_fn; return t->pos; } void qb_log_custom_close(int32_t t) { struct qb_log_target *target; if (!logger_inited) { return; } if (t < 0 || t >= QB_LOG_TARGET_MAX || conf[t].state == QB_LOG_STATE_UNUSED) { return; } target = qb_log_target_get(t); if (target->close) { in_logger = QB_TRUE; target->close(t); in_logger = QB_FALSE; } qb_log_target_free(target); } static int32_t _log_target_enable(struct qb_log_target *t) { int32_t rc = 0; if (t->state == QB_LOG_STATE_ENABLED) { return 0; } if (t->pos == QB_LOG_STDERR || t->pos == QB_LOG_STDOUT) { rc = qb_log_stderr_open(t); } else if (t->pos == QB_LOG_SYSLOG) { rc = qb_log_syslog_open(t); } else if (t->pos == QB_LOG_BLACKBOX) { rc = qb_log_blackbox_open(t); } if (rc == 0) { _log_target_state_set(t, QB_LOG_STATE_ENABLED); } return rc; } static void _log_target_disable(struct qb_log_target *t) { if (t->state != QB_LOG_STATE_ENABLED) { return; } _log_target_state_set(t, QB_LOG_STATE_DISABLED); if (t->close) { in_logger = QB_TRUE; t->close(t->pos); in_logger = QB_FALSE; } } int32_t qb_log_ctl(int32_t t, enum qb_log_conf c, int32_t arg) { int32_t rc = 0; int32_t need_reload = QB_FALSE; if (!logger_inited) { return -EINVAL; } if (t < 0 || t >= QB_LOG_TARGET_MAX || conf[t].state == QB_LOG_STATE_UNUSED) { return -EBADF; } switch (c) { case QB_LOG_CONF_ENABLED: if (arg) { rc = _log_target_enable(&conf[t]); } else { _log_target_disable(&conf[t]); } break; case QB_LOG_CONF_STATE_GET: rc = conf[t].state; break; case QB_LOG_CONF_FACILITY: conf[t].facility = arg; if (t == QB_LOG_SYSLOG) { need_reload = QB_TRUE; } break; case QB_LOG_CONF_FILE_SYNC: conf[t].file_sync = arg; break; case QB_LOG_CONF_PRIORITY_BUMP: conf[t].priority_bump = arg; break; case QB_LOG_CONF_SIZE: if (t == QB_LOG_BLACKBOX) { if (arg <= 0) { return -EINVAL; } conf[t].size = arg; need_reload = QB_TRUE; } else { return -ENOSYS; } break; case QB_LOG_CONF_THREADED: conf[t].threaded = arg; break; default: rc = -EINVAL; } if (rc == 0 && need_reload && conf[t].reload) { in_logger = QB_TRUE; conf[t].reload(t); in_logger = QB_FALSE; } return rc; } diff --git a/lib/log_thread.c b/lib/log_thread.c index 0e02f22..3dffef9 100644 --- a/lib/log_thread.c +++ b/lib/log_thread.c @@ -1,279 +1,279 @@ /* * Copyright (C) 2011 Red Hat, Inc. * * All rights reserved. * * Author: Angus Salkeld * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include #include #include #include #include #include "log_int.h" static int wthread_active = 0; static int wthread_should_exit = 0; static qb_thread_lock_t *logt_wthread_lock = NULL; static QB_LIST_DECLARE(logt_print_finished_records); static int logt_memory_used = 0; static int logt_dropped_messages = 0; static sem_t logt_thread_start; static sem_t logt_print_finished; static int logt_sched_param_queued = QB_FALSE; static int logt_sched_policy; #if defined(HAVE_PTHREAD_SETSCHEDPARAM) && defined(HAVE_SCHED_GET_PRIORITY_MAX) static struct sched_param logt_sched_param; #endif /* HAVE_PTHREAD_SETSCHEDPARAM && HAVE_SCHED_GET_PRIORITY_MAX */ static pthread_t logt_thread_id = 0; static void *qb_logt_worker_thread(void *data) __attribute__ ((noreturn)); static void * qb_logt_worker_thread(void *data) { struct qb_log_record *rec; int dropped = 0; int res; /* * Signal wthread_create that the initialization process may continue */ sem_post(&logt_thread_start); for (;;) { retry_sem_wait: res = sem_wait(&logt_print_finished); if (res == -1 && errno == EINTR) { goto retry_sem_wait; } else if (res == -1) { /* * This case shouldn't happen */ pthread_exit(NULL); } (void)qb_thread_lock(logt_wthread_lock); if (wthread_should_exit) { int value = -1; (void)sem_getvalue(&logt_print_finished, &value); if (value == 0) { (void)qb_thread_unlock(logt_wthread_lock); pthread_exit(NULL); } } rec = - qb_list_entry(logt_print_finished_records.next, + qb_list_first_entry(&logt_print_finished_records, struct qb_log_record, list); qb_list_del(&rec->list); logt_memory_used = logt_memory_used - strlen(rec->buffer) - sizeof(struct qb_log_record) - 1; dropped = logt_dropped_messages; logt_dropped_messages = 0; (void)qb_thread_unlock(logt_wthread_lock); if (dropped) { printf("%d messages lost\n", dropped); } qb_log_thread_log_write(rec->cs, rec->timestamp, rec->buffer); free(rec->buffer); free(rec); } } int32_t qb_log_thread_priority_set(int32_t policy, int32_t priority) { int res = 0; #if defined(HAVE_PTHREAD_SETSCHEDPARAM) && defined(HAVE_SCHED_GET_PRIORITY_MAX) logt_sched_policy = policy; if (policy == SCHED_OTHER #ifdef SCHED_IDLE || policy == SCHED_IDLE #endif #if defined(SCHED_BATCH) && !defined(QB_DARWIN) || policy == SCHED_BATCH #endif ) { logt_sched_param.sched_priority = 0; } else { logt_sched_param.sched_priority = priority; } if (wthread_active == 0) { logt_sched_param_queued = QB_TRUE; } else { res = pthread_setschedparam(logt_thread_id, policy, &logt_sched_param); if (res != 0) { res = -res; } } #endif return res; } int32_t qb_log_thread_start(void) { int res; if (wthread_active) { return 0; } wthread_active = 1; sem_init(&logt_thread_start, 0, 0); sem_init(&logt_print_finished, 0, 0); res = pthread_create(&logt_thread_id, NULL, qb_logt_worker_thread, NULL); if (res != 0) { wthread_active = 0; return -res; } sem_wait(&logt_thread_start); if (logt_sched_param_queued) { res = qb_log_thread_priority_set(logt_sched_policy, logt_sched_param.sched_priority); if (res != 0) { goto cleanup_pthread; } logt_sched_param_queued = QB_FALSE; } logt_wthread_lock = qb_thread_lock_create(QB_THREAD_LOCK_SHORT); if (logt_wthread_lock == NULL) { goto cleanup_pthread; } return 0; cleanup_pthread: wthread_should_exit = 1; sem_post(&logt_print_finished); pthread_join(logt_thread_id, NULL); sem_destroy(&logt_print_finished); sem_destroy(&logt_thread_start); return res; } void qb_log_thread_log_post(struct qb_log_callsite *cs, time_t timestamp, const char *buffer) { struct qb_log_record *rec; size_t buf_size; size_t total_size; rec = malloc(sizeof(struct qb_log_record)); if (rec == NULL) { return; } buf_size = strlen(buffer) + 1; total_size = sizeof(struct qb_log_record) + buf_size; rec->cs = cs; rec->buffer = malloc(buf_size); if (rec->buffer == NULL) { goto free_record; } memcpy(rec->buffer, buffer, buf_size); rec->timestamp = timestamp; qb_list_init(&rec->list); (void)qb_thread_lock(logt_wthread_lock); logt_memory_used += total_size; if (logt_memory_used > 512000) { free(rec->buffer); free(rec); logt_memory_used = logt_memory_used - total_size; logt_dropped_messages += 1; (void)qb_thread_unlock(logt_wthread_lock); return; } else { qb_list_add_tail(&rec->list, &logt_print_finished_records); } (void)qb_thread_unlock(logt_wthread_lock); sem_post(&logt_print_finished); return; free_record: free(rec); } void qb_log_thread_stop(void) { int res; int value; struct qb_log_record *rec; if (wthread_active == 0 && logt_wthread_lock == NULL) { return; } if (wthread_active == 0) { for (;;) { res = sem_getvalue(&logt_print_finished, &value); if (res != 0 || value == 0) { return; } sem_wait(&logt_print_finished); (void)qb_thread_lock(logt_wthread_lock); - rec = qb_list_entry(logt_print_finished_records.next, + rec = qb_list_first_entry(&logt_print_finished_records, struct qb_log_record, list); qb_list_del(&rec->list); logt_memory_used = logt_memory_used - strlen(rec->buffer) - sizeof(struct qb_log_record) - 1; (void)qb_thread_unlock(logt_wthread_lock); qb_log_thread_log_write(rec->cs, rec->timestamp, rec->buffer); free(rec->buffer); free(rec); } } else { wthread_should_exit = 1; sem_post(&logt_print_finished); pthread_join(logt_thread_id, NULL); } (void)qb_thread_lock_destroy(logt_wthread_lock); sem_destroy(&logt_print_finished); sem_destroy(&logt_thread_start); } diff --git a/lib/loop.c b/lib/loop.c index 0d164b7..5d21284 100644 --- a/lib/loop.c +++ b/lib/loop.c @@ -1,214 +1,212 @@ /* * Copyright (C) 2010 Red Hat, Inc. * * Author: Angus Salkeld * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include #include #include #include "loop_int.h" #include "util_int.h" static struct qb_loop *default_intance = NULL; static void qb_loop_run_level(struct qb_loop_level *level) { struct qb_loop_item *job; - struct qb_list_head *iter; int32_t processed = 0; Ill_have_another: - iter = level->job_head.next; - if (iter != &level->job_head) { - job = qb_list_entry(iter, struct qb_loop_item, list); + if (!qb_list_empty(&level->job_head)) { + job = qb_list_first_entry(&level->job_head, struct qb_loop_item, list); qb_list_del(&job->list); qb_list_init(&job->list); job->source->dispatch_and_take_back(job, level->priority); level->todo--; processed++; if (level->l->stop_requested) { return; } if (processed < level->to_process) { goto Ill_have_another; } } } void qb_loop_level_item_add(struct qb_loop_level *level, struct qb_loop_item *job) { qb_list_init(&job->list); qb_list_add_tail(&job->list, &level->job_head); level->todo++; } void qb_loop_level_item_del(struct qb_loop_level *level, struct qb_loop_item *job) { qb_list_del(&job->list); qb_list_init(&job->list); level->todo--; } struct qb_loop * qb_loop_default_get(void) { return default_intance; } struct qb_loop * qb_loop_create(void) { struct qb_loop *l = malloc(sizeof(struct qb_loop)); int32_t p; if (l == NULL) { return NULL; } for (p = QB_LOOP_LOW; p <= QB_LOOP_HIGH; p++) { l->level[p].priority = p; l->level[p].to_process = 4; l->level[p].todo = 0; l->level[p].l = l; qb_list_init(&l->level[p].job_head); qb_list_init(&l->level[p].wait_head); } l->stop_requested = QB_FALSE; l->timer_source = qb_loop_timer_create(l); l->job_source = qb_loop_jobs_create(l); l->fd_source = qb_loop_poll_create(l); l->signal_source = qb_loop_signals_create(l); if (default_intance == NULL) { default_intance = l; } return l; } void qb_loop_destroy(struct qb_loop *l) { qb_loop_timer_destroy(l); qb_loop_jobs_destroy(l); qb_loop_poll_destroy(l); qb_loop_signals_destroy(l); if (default_intance == l) { default_intance = NULL; } free(l); } void qb_loop_stop(struct qb_loop *l) { if (l == NULL) { default_intance->stop_requested = QB_TRUE; } else { l->stop_requested = QB_TRUE; } } void qb_loop_run(struct qb_loop *lp) { int32_t p; int32_t p_stop = QB_LOOP_LOW; int32_t rc; int32_t remaining_todo = 0; int32_t job_todo; int32_t timer_todo; int32_t ms_timeout; struct qb_loop *l = lp; if (l == NULL) { l = default_intance; } l->stop_requested = QB_FALSE; do { if (p_stop == QB_LOOP_LOW) { p_stop = QB_LOOP_HIGH; } else { p_stop--; } job_todo = 0; if (l->job_source && l->job_source->poll) { rc = l->job_source->poll(l->job_source, 0); if (rc > 0) { job_todo = rc; } else if (rc == -1) { errno = -rc; qb_util_perror(LOG_WARNING, "job->poll"); } } timer_todo = 0; if (l->timer_source && l->timer_source->poll) { rc = l->timer_source->poll(l->timer_source, 0); if (rc > 0) { timer_todo = rc; } else if (rc == -1) { errno = -rc; qb_util_perror(LOG_WARNING, "timer->poll"); } } if (remaining_todo > 0 || timer_todo > 0) { /* * if there are remaining todos or timer todos then don't wait. */ ms_timeout = 0; } else if (job_todo > 0) { /* * if we only have jobs to do (not timers or old todos) * then set a non-zero timeout. Jobs can spin out of * control if someone keeps adding them. */ ms_timeout = 50; } else { if (l->timer_source) { ms_timeout = qb_loop_timer_msec_duration_to_expire(l->timer_source); } else { ms_timeout = -1; } } rc = l->fd_source->poll(l->fd_source, ms_timeout); if (rc < 0) { errno = -rc; qb_util_perror(LOG_WARNING, "fd->poll"); } remaining_todo = 0; for (p = QB_LOOP_HIGH; p >= QB_LOOP_LOW; p--) { if (p >= p_stop) { qb_loop_run_level(&l->level[p]); if (l->stop_requested) { return; } } remaining_todo += l->level[p].todo; } } while (!l->stop_requested); } diff --git a/lib/loop_job.c b/lib/loop_job.c index 178f816..1d8cd49 100644 --- a/lib/loop_job.c +++ b/lib/loop_job.c @@ -1,168 +1,168 @@ /* * Copyright (C) 2006-2010 Red Hat, Inc. * * Author: Angus Salkeld * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include "os_base.h" #include #include #include #include "loop_int.h" #include "util_int.h" struct qb_loop_job { struct qb_loop_item item; qb_loop_job_dispatch_fn dispatch_fn; }; static void job_dispatch(struct qb_loop_item *item, enum qb_loop_priority p) { struct qb_loop_job *job = qb_list_entry(item, struct qb_loop_job, item); job->dispatch_fn(job->item.user_data); free(job); /* * this is a one-shot so don't re-add */ } static int32_t get_more_jobs(struct qb_loop_source *s, int32_t ms_timeout) { int32_t p; int32_t new_jobs = 0; int32_t level_jobs = 0; /* * this is simple, move jobs from wait_head to job_head */ for (p = QB_LOOP_LOW; p <= QB_LOOP_HIGH; p++) { if (!qb_list_empty(&s->l->level[p].wait_head)) { level_jobs = qb_list_length(&s->l->level[p].wait_head); new_jobs += level_jobs; - qb_list_splice(&s->l->level[p].wait_head, - s->l->level[p].job_head.prev); + qb_list_splice_tail(&s->l->level[p].wait_head, + &s->l->level[p].job_head); qb_list_init(&s->l->level[p].wait_head); s->l->level[p].todo += level_jobs; } } return new_jobs; } struct qb_loop_source * qb_loop_jobs_create(struct qb_loop *l) { struct qb_loop_source *s = malloc(sizeof(struct qb_loop_source)); if (s == NULL) { return NULL; } s->l = l; s->dispatch_and_take_back = job_dispatch; s->poll = get_more_jobs; return s; } void qb_loop_jobs_destroy(struct qb_loop *l) { free(l->job_source); } int32_t qb_loop_job_add(struct qb_loop *lp, enum qb_loop_priority p, void *data, qb_loop_job_dispatch_fn dispatch_fn) { struct qb_loop_job *job; struct qb_loop *l = lp; if (l == NULL) { l = qb_loop_default_get(); } if (l == NULL || dispatch_fn == NULL) { return -EINVAL; } if (p < QB_LOOP_LOW || p > QB_LOOP_HIGH) { return -EINVAL; } job = malloc(sizeof(struct qb_loop_job)); if (job == NULL) { return -ENOMEM; } job->dispatch_fn = dispatch_fn; job->item.user_data = data; job->item.source = l->job_source; job->item.type = QB_LOOP_JOB; qb_list_init(&job->item.list); qb_list_add_tail(&job->item.list, &l->level[p].wait_head); return 0; } int32_t qb_loop_job_del(struct qb_loop *lp, enum qb_loop_priority p, void *data, qb_loop_job_dispatch_fn dispatch_fn) { struct qb_loop_job *job; struct qb_loop_item *item; struct qb_loop *l = lp; if (l == NULL) { l = qb_loop_default_get(); } if (l == NULL || dispatch_fn == NULL) { return -EINVAL; } if (p > QB_LOOP_HIGH) { return -EINVAL; } qb_list_for_each_entry(item, &l->level[p].wait_head, list) { job = (struct qb_loop_job *)item; if (job->dispatch_fn == dispatch_fn && job->item.user_data == data && job->item.type == QB_LOOP_JOB) { qb_list_del(&job->item.list); free(job); return 0; } } qb_list_for_each_entry(item, &l->level[p].job_head, list) { if (item->type != QB_LOOP_JOB) { continue; } job = (struct qb_loop_job *)item; if (job->dispatch_fn == dispatch_fn && job->item.user_data == data) { qb_loop_level_item_del(&l->level[p], item); qb_util_log(LOG_DEBUG, "deleting job in JOBLIST"); return 0; } } return -ENOENT; } diff --git a/lib/skiplist.c b/lib/skiplist.c index c6c89a2..ac80f20 100644 --- a/lib/skiplist.c +++ b/lib/skiplist.c @@ -1,564 +1,559 @@ /* * Copyright (C) 2011 Red Hat, Inc. * * Author: Angus Salkeld * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include #include #include #include #include "map_int.h" #define SKIPLIST_LEVEL_MAX 8 #define SKIPLIST_LEVEL_MIN 0 /* The amount of possible levels */ #define SKIPLIST_LEVEL_COUNT (SKIPLIST_LEVEL_MAX - SKIPLIST_LEVEL_MIN + 1) struct skiplist_iter { struct qb_map_iter i; struct skiplist_node *n; }; struct skiplist_node { const char *key; void *value; int8_t level; uint32_t refcount; struct qb_list_head notifier_head; /* An array of @level + 1 node pointers */ struct skiplist_node **forward; }; struct skiplist { struct qb_map map; size_t length; int8_t level; struct skiplist_node *header; }; /* An array of nodes that need to be updated after an insert or delete operation */ typedef struct skiplist_node *skiplist_update_t[SKIPLIST_LEVEL_COUNT]; static int8_t skiplist_level_generate(void) { /* This constant is found by 1 / P, where P = 0.25. */ enum { P_INVERSE = 4 }; /* The original algorithm's random number is in the range [0, 1), so * max M = 1. Its ceiling C = M * P = 1 * P = P. * * Our random number is in the range [0, UINT16_MAX], so M = UINT16_MAX. Therefore, * C = UINT16_MAX * P = UINT16_MAX / P_INVERSE. */ enum { P_CEIL = UINT16_MAX / P_INVERSE }; int8_t level = SKIPLIST_LEVEL_MIN; while ((uint16_t) (random()) < P_CEIL) level++; if (level < SKIPLIST_LEVEL_MAX) return level; return SKIPLIST_LEVEL_MAX; } static struct skiplist_node * skiplist_node_next(const struct skiplist_node *node) { const struct skiplist_node *n = node; do { n = n->forward[SKIPLIST_LEVEL_MIN]; } while (n && n->refcount == 0); return (struct skiplist_node *)n; } /* * Create a new level @level node with value @value. The node should eventually * be destroyed with @skiplist_node_destroy. * * return: a new node on success and NULL otherwise. */ static struct skiplist_node * skiplist_node_new(const int8_t level, const char *key, const void *value) { struct skiplist_node *new_node = (struct skiplist_node *) (malloc(sizeof(struct skiplist_node))); if (!new_node) return NULL; new_node->value = (void *)value; new_node->key = key; new_node->level = level; new_node->refcount = 1; qb_list_init(&new_node->notifier_head); /* A level 0 node still needs to hold 1 forward pointer, etc. */ new_node->forward = (struct skiplist_node **) (calloc(level + 1, sizeof(struct skiplist_node *))); if (new_node->forward == NULL) { free(new_node); return NULL; } return new_node; } static struct skiplist_node * skiplist_header_node_new(void) { return skiplist_node_new(SKIPLIST_LEVEL_MAX, NULL, NULL); } /* An operation to perform after comparing a user value or search with a * node's value */ typedef enum { OP_GOTO_NEXT_LEVEL, OP_GOTO_NEXT_NODE, OP_FINISH, } op_t; static op_t op_search(const struct skiplist *list, const struct skiplist_node *fwd_node, const void *search) { int32_t cmp; if (!fwd_node) return OP_GOTO_NEXT_LEVEL; cmp = strcmp(fwd_node->key, search); if (cmp < 0) { return OP_GOTO_NEXT_NODE; } else if (cmp == 0) { return OP_FINISH; } return OP_GOTO_NEXT_LEVEL; } static struct skiplist_node * skiplist_lookup(struct skiplist *list, const char *key) { struct skiplist_node *cur_node = list->header; int8_t level = list->level; while (level >= SKIPLIST_LEVEL_MIN) { struct skiplist_node *fwd_node = cur_node->forward[level]; switch (op_search(list, fwd_node, key)) { case OP_FINISH: return fwd_node; case OP_GOTO_NEXT_NODE: cur_node = fwd_node; break; case OP_GOTO_NEXT_LEVEL: level--; } } return NULL; } static void skiplist_notify(struct skiplist *l, struct skiplist_node *n, uint32_t event, char *key, void *old_value, void *value) { struct qb_list_head *list; struct qb_map_notifier *tn; /* node callbacks */ - for (list = n->notifier_head.next; - list != &n->notifier_head; list = list->next) { + qb_list_for_each(list, &n->notifier_head) { tn = qb_list_entry(list, struct qb_map_notifier, list); if (tn->events & event) { tn->callback(event, key, old_value, value, tn->user_data); } } /* global callbacks */ - for (list = l->header->notifier_head.next; - list != &l->header->notifier_head; list = list->next) { + qb_list_for_each(list, &l->header->notifier_head) { tn = qb_list_entry(list, struct qb_map_notifier, list); if (tn->events & event) { tn->callback(event, key, old_value, value, tn->user_data); } if (((event & QB_MAP_NOTIFY_DELETED) || (event & QB_MAP_NOTIFY_REPLACED)) && (tn->events & QB_MAP_NOTIFY_FREE)) { tn->callback(QB_MAP_NOTIFY_FREE, (char *)key, old_value, value, tn->user_data); } } } static void skiplist_node_destroy(struct skiplist_node *node, struct skiplist *list) { skiplist_notify(list, node, QB_MAP_NOTIFY_DELETED, (char *)node->key, node->value, NULL); free(node->forward); free(node); } static void skiplist_node_deref(struct skiplist_node *node, struct skiplist *list) { node->refcount--; if (node->refcount == 0) { skiplist_node_destroy(node, list); } } static int32_t skiplist_notify_add(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, void *user_data) { struct skiplist *t = (struct skiplist *)m; struct qb_map_notifier *f; struct skiplist_node *n; struct qb_list_head *list; int add_to_tail = QB_FALSE; if (key) { n = skiplist_lookup(t, key); } else { n = t->header; } if (events & QB_MAP_NOTIFY_FREE) { add_to_tail = QB_TRUE; } if (n) { - for (list = n->notifier_head.next; - list != &n->notifier_head; list = list->next) { + qb_list_for_each(list, &n->notifier_head) { f = qb_list_entry(list, struct qb_map_notifier, list); if (events & QB_MAP_NOTIFY_FREE && f->events == events) { /* only one free notifier */ return -EEXIST; } if (f->events == events && f->callback == fn && f->user_data == user_data) { return -EEXIST; } } f = malloc(sizeof(struct qb_map_notifier)); if (f == NULL) { return -errno; } f->events = events; f->user_data = user_data; f->callback = fn; qb_list_init(&f->list); if (add_to_tail) { qb_list_add_tail(&f->list, &n->notifier_head); } else { qb_list_add(&f->list, &n->notifier_head); } return 0; } return -EINVAL; } static int32_t skiplist_notify_del(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, int32_t cmp_userdata, void *user_data) { struct skiplist *t = (struct skiplist *)m; struct skiplist_node *n; struct qb_map_notifier *f; struct qb_list_head *head = NULL; struct qb_list_head *list; struct qb_list_head *next; int32_t found = QB_FALSE; if (key) { n = skiplist_lookup(t, key); if (n) { head = &n->notifier_head; } } else { head = &t->header->notifier_head; } if (head == NULL) { return -ENOENT; } - for (list = head->next; - list != head; list = next) { + qb_list_for_each_safe(list, next, head) { f = qb_list_entry(list, struct qb_map_notifier, list); - next = list->next; if (f->events == events && f->callback == fn) { if (cmp_userdata && (f->user_data == user_data)) { found = QB_TRUE; qb_list_del(&f->list); free(f); } else if (!cmp_userdata) { found = QB_TRUE; qb_list_del(&f->list); free(f); } } } if (found) { return 0; } else { return -ENOENT; } } static void skiplist_destroy(struct qb_map *map) { struct skiplist *list = (struct skiplist *)map; struct skiplist_node *cur_node; struct skiplist_node *fwd_node; for (cur_node = skiplist_node_next(list->header); cur_node; cur_node = fwd_node) { fwd_node = skiplist_node_next(cur_node); skiplist_node_destroy(cur_node, list); } skiplist_node_destroy(list->header, list); free(list); } static void skiplist_put(struct qb_map *map, const char *key, const void *value) { struct skiplist *list = (struct skiplist *)map; struct skiplist_node *new_node; int8_t level = list->level; skiplist_update_t update; int8_t update_level; int8_t new_node_level; struct skiplist_node *cur_node = list->header; char *old_k; char *old_v; while ((update_level = level) >= SKIPLIST_LEVEL_MIN) { struct skiplist_node *fwd_node = cur_node->forward[level]; switch (op_search(list, fwd_node, key)) { case OP_FINISH: old_k = (char *)fwd_node->key; old_v = (char *)fwd_node->value; fwd_node->value = (void *)value; fwd_node->key = (void *)key; skiplist_notify(list, fwd_node, QB_MAP_NOTIFY_REPLACED, old_k, old_v, fwd_node->value); return; case OP_GOTO_NEXT_NODE: cur_node = fwd_node; break; case OP_GOTO_NEXT_LEVEL: level--; } update[update_level] = cur_node; } new_node_level = skiplist_level_generate(); if (new_node_level > list->level) { for (level = list->level + 1; level <= new_node_level; level++) update[level] = list->header; list->level = new_node_level; } new_node = skiplist_node_new(new_node_level, key, value); assert(new_node != NULL); skiplist_notify(list, new_node, QB_MAP_NOTIFY_INSERTED, (char*)new_node->key, NULL, new_node->value); /* Drop @new_node into @list. */ for (level = SKIPLIST_LEVEL_MIN; level <= new_node_level; level++) { new_node->forward[level] = update[level]->forward[level]; update[level]->forward[level] = new_node; } list->length++; } static int32_t skiplist_rm(struct qb_map *map, const char *key) { struct skiplist *list = (struct skiplist *)map; struct skiplist_node *found_node; struct skiplist_node *cur_node = list->header; int8_t level = list->level; int8_t update_level; skiplist_update_t update; while ((update_level = level) >= SKIPLIST_LEVEL_MIN) { struct skiplist_node *fwd_node = cur_node->forward[level]; switch (op_search(list, fwd_node, key)) { case OP_GOTO_NEXT_NODE: cur_node = fwd_node; break; case OP_GOTO_NEXT_LEVEL: default: level--; break; } update[update_level] = cur_node; } /* The immediate forward node should be the matching node... */ found_node = skiplist_node_next(cur_node); /* ...unless we're at the end of the list or the value doesn't exist. */ if (!found_node || strcmp(found_node->key, key) != 0) { return QB_FALSE; } /* Splice found_node out of list. */ for (level = SKIPLIST_LEVEL_MIN; level <= list->level; level++) if (update[level]->forward[level] == found_node) update[level]->forward[level] = found_node->forward[level]; skiplist_node_deref(found_node, list); /* Remove unused levels from @list -- stop removing levels as soon as a * used level is found. Unused levels can occur if @found_node had the * highest level. */ for (level = list->level; level >= SKIPLIST_LEVEL_MIN; level--) { if (list->header->forward[level]) break; list->level--; } list->length--; return QB_TRUE; } static void * skiplist_get(struct qb_map *map, const char *key) { struct skiplist *list = (struct skiplist *)map; struct skiplist_node *n = skiplist_lookup(list, key); if (n) { return n->value; } return NULL; } static qb_map_iter_t * skiplist_iter_create(struct qb_map *map, const char *prefix) { struct skiplist_iter *i = malloc(sizeof(struct skiplist_iter)); struct skiplist *list = (struct skiplist *)map; if (i == NULL) { return NULL; } i->i.m = map; i->n = list->header; i->n->refcount++; return (qb_map_iter_t *) i; } static const char * skiplist_iter_next(qb_map_iter_t * i, void **value) { struct skiplist_iter *si = (struct skiplist_iter *)i; struct skiplist_node *p = si->n; if (p == NULL) { return NULL; } si->n = skiplist_node_next(p); if (si->n == NULL) { skiplist_node_deref(p, (struct skiplist *)i->m); return NULL; } si->n->refcount++; skiplist_node_deref(p, (struct skiplist *)i->m); *value = si->n->value; return si->n->key; } static void skiplist_iter_free(qb_map_iter_t * i) { free(i); } static size_t skiplist_count_get(struct qb_map *map) { struct skiplist *list = (struct skiplist *)map; return list->length; } qb_map_t * qb_skiplist_create(void) { struct skiplist *sl = malloc(sizeof(struct skiplist)); if (sl == NULL) { return NULL; } srand(time(NULL)); sl->map.put = skiplist_put; sl->map.get = skiplist_get; sl->map.rm = skiplist_rm; sl->map.count_get = skiplist_count_get; sl->map.iter_create = skiplist_iter_create; sl->map.iter_next = skiplist_iter_next; sl->map.iter_free = skiplist_iter_free; sl->map.destroy = skiplist_destroy; sl->map.notify_add = skiplist_notify_add; sl->map.notify_del = skiplist_notify_del; sl->level = SKIPLIST_LEVEL_MIN; sl->length = 0; sl->header = skiplist_header_node_new(); return (qb_map_t *) sl; } diff --git a/lib/trie.c b/lib/trie.c index 089a16f..56001a2 100644 --- a/lib/trie.c +++ b/lib/trie.c @@ -1,803 +1,797 @@ /* * Copyright (C) 2011 Red Hat, Inc. * * Author: Angus Salkeld * * This file is part of libqb. * * libqb is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation, either version 2.1 of the License, or * (at your option) any later version. * * libqb 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 Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with libqb. If not, see . */ #include #include #include #include #include #include "map_int.h" struct trie_iter { struct qb_map_iter i; const char *prefix; struct trie_node *n; struct trie_node *root; }; struct trie_node { uint32_t idx; char *segment; uint32_t num_segments; char *key; void *value; struct trie_node **children; uint32_t num_children; uint32_t refcount; struct trie_node *parent; struct qb_list_head notifier_head; }; struct trie { struct qb_map map; size_t length; uint32_t num_nodes; uint32_t mem_used; struct trie_node *header; }; static void trie_notify(struct trie_node *n, uint32_t event, const char *key, void *old_value, void *value); static struct trie_node *trie_new_node(struct trie *t, struct trie_node *parent); /* * characters are stored in reverse to make accessing the * more common case (non-control chars) more space efficient. */ #define TRIE_CHAR2INDEX(ch) (126 - ch) #define TRIE_INDEX2CHAR(idx) (126 - idx) static int32_t trie_node_alive(struct trie_node *node) { if (node->value == NULL || node->refcount <= 0) { return QB_FALSE; } return QB_TRUE; } static struct trie_node * trie_node_next(struct trie_node *node, struct trie_node *root, int all) { struct trie_node *c = node; struct trie_node *n; struct trie_node *p; int i; keep_going: n = NULL; /* child/outward */ for (i = c->num_children - 1; i >= 0; i--) { if (c->children[i]) { n = c->children[i]; break; } } if (n) { if (all || trie_node_alive(n)) { return n; } else { c = n; goto keep_going; } } /* sibling/parent */ if (c == root) { return NULL; } p = c; do { for (i = p->idx - 1; i >= 0; i--) { if (p->parent->children[i]) { n = p->parent->children[i]; break; } } if (n == NULL) { p = p->parent; } } while (n == NULL && p != root); if (n) { if (all || trie_node_alive(n)) { return n; } if (n == root) { return NULL; } c = n; goto keep_going; } return n; } static struct trie_node * new_child_node(struct trie *t, struct trie_node * parent, char ch) { struct trie_node *new_node; int old_max_idx; int i; int idx = TRIE_CHAR2INDEX(ch); if (idx >= parent->num_children) { old_max_idx = parent->num_children; parent->num_children = QB_MAX(idx + 1, 30); t->mem_used += (sizeof(struct trie_node*) * (parent->num_children - old_max_idx)); parent->children = realloc(parent->children, (parent->num_children * sizeof(struct trie_node*))); if (parent->children == NULL) { return NULL; } for (i = old_max_idx; i < parent->num_children; i++) { parent->children[i] = NULL; } } new_node = trie_new_node(t, parent); if (new_node == NULL) { return NULL; } new_node->idx = idx; parent->children[idx] = new_node; return new_node; } static struct trie_node * trie_node_split(struct trie *t, struct trie_node *cur_node, int seg_cnt) { struct trie_node *split_node; struct trie_node ** children = cur_node->children; uint32_t num_children = cur_node->num_children; int i; int s; cur_node->children = NULL; cur_node->num_children = 0; split_node = new_child_node(t, cur_node, cur_node->segment[seg_cnt]); if (split_node == NULL) { return NULL; } split_node->children = children; split_node->num_children = num_children; for (i = 0; i < split_node->num_children; i++) { if (split_node->children[i]) { split_node->children[i]->parent = split_node; } } split_node->value = cur_node->value; split_node->key = cur_node->key; split_node->refcount = cur_node->refcount; cur_node->value = NULL; cur_node->key = NULL; cur_node->refcount = 0; /* move notifier list to split */ - split_node->notifier_head.next = cur_node->notifier_head.next; - split_node->notifier_head.next->prev = &split_node->notifier_head; - split_node->notifier_head.prev = cur_node->notifier_head.prev; - split_node->notifier_head.prev->next = &split_node->notifier_head; + qb_list_replace(&cur_node->notifier_head, &split_node->notifier_head); qb_list_init(&cur_node->notifier_head); if (seg_cnt < cur_node->num_segments) { split_node->num_segments = cur_node->num_segments - seg_cnt - 1; split_node->segment = malloc(split_node->num_segments * sizeof(char)); if (split_node->segment == NULL) { free(split_node); return NULL; } for (i = (seg_cnt + 1); i < cur_node->num_segments; i++) { s = i - seg_cnt - 1; split_node->segment[s] = cur_node->segment[i]; cur_node->segment[i] = '\0'; } cur_node->num_segments = seg_cnt; } return cur_node; } static struct trie_node * trie_insert(struct trie *t, const char *key) { struct trie_node *cur_node = t->header; struct trie_node *new_node; char *cur = (char *)key; int idx = TRIE_CHAR2INDEX(key[0]); int seg_cnt = 0; do { new_node = NULL; if (cur_node->num_segments > 0 && seg_cnt < cur_node->num_segments) { if (cur_node->segment[seg_cnt] == *cur) { /* we found the char in the segment */ seg_cnt++; } else { cur_node = trie_node_split(t, cur_node, seg_cnt); if (cur_node == NULL) { return NULL; } new_node = new_child_node(t, cur_node, *cur); if (new_node == NULL) { return NULL; } } } else if (idx < cur_node->num_children && cur_node->children[idx]) { /* the char can be found on the next node */ new_node = cur_node->children[idx]; } else if (cur_node == t->header) { /* the root node is empty so make it on the next node */ new_node = new_child_node(t, cur_node, *cur); if (new_node == NULL) { return NULL; } } else if (cur_node->value == NULL && qb_list_empty(&cur_node->notifier_head) && cur_node->num_children == 0 && seg_cnt == cur_node->num_segments) { /* we are on a leaf (with no value) so just add it as a segment */ cur_node->segment = realloc(cur_node->segment, cur_node->num_segments + 1); cur_node->segment[cur_node->num_segments] = *cur; t->mem_used += sizeof(char); cur_node->num_segments++; seg_cnt++; } else if (seg_cnt == cur_node->num_segments) { /* on the last segment need to make a new node */ new_node = new_child_node(t, cur_node, *cur); if (new_node == NULL) { return NULL; } } else /* need_to_split */ { cur_node = trie_node_split(t, cur_node, seg_cnt); if (cur_node == NULL) { return NULL; } new_node = new_child_node(t, cur_node, *cur); if (new_node == NULL) { return NULL; } } if (new_node) { seg_cnt = 0; cur_node = new_node; } cur++; idx = TRIE_CHAR2INDEX(*cur); } while (*cur != '\0'); if (cur_node->num_segments > 0 && seg_cnt < cur_node->num_segments) { /* we need to split */ cur_node = trie_node_split(t, cur_node, seg_cnt); if (cur_node == NULL) { return NULL; } new_node = new_child_node(t, cur_node, *cur); if (new_node == NULL) { return NULL; } } return cur_node; } static struct trie_node * trie_lookup(struct trie *t, const char *key, int exact_match) { struct trie_node *cur_node = t->header; char *cur = (char *)key; int idx = TRIE_CHAR2INDEX(key[0]); int seg_cnt = 0; do { if (cur_node->num_segments > 0 && seg_cnt < cur_node->num_segments) { if (cur_node->segment[seg_cnt] == *cur) { /* we found the char in the segment */ seg_cnt++; } else { return NULL; } } else if (idx < cur_node->num_children && cur_node->children[idx]) { /* the char can be found on the next node */ cur_node = cur_node->children[idx]; seg_cnt = 0; } else { return NULL; } cur++; idx = TRIE_CHAR2INDEX(*cur); } while (*cur != '\0'); if (exact_match && cur_node->num_segments > 0 && seg_cnt < cur_node->num_segments) { return NULL; } return cur_node; } static void trie_node_release(struct trie *t, struct trie_node *node) { int i; int empty = QB_FALSE; if (node->key == NULL && node->parent != NULL && qb_list_empty(&node->notifier_head)) { struct trie_node *p = node->parent; if (node->num_children == 0) { empty = QB_TRUE; } else { empty = QB_TRUE; for (i = node->num_children - 1; i >= 0; i--) { if (node->children[i]) { empty = QB_FALSE; break; } } } if (!empty) { return; } /* * unlink the node from the parent */ p->children[node->idx] = NULL; free(node->segment); free(node->children); free(node); t->num_nodes--; t->mem_used -= sizeof(struct trie_node); trie_node_release(t, p); } } static void trie_node_destroy(struct trie *t, struct trie_node *n) { if (n->value == NULL) { return; } trie_notify(n, QB_MAP_NOTIFY_DELETED, n->key, n->value, NULL); n->key = NULL; n->value = NULL; trie_node_release(t, n); } static void trie_print_node(struct trie_node *n, struct trie_node *r, const char *suffix) { int i; if (n->parent) { trie_print_node(n->parent, n, suffix); } if (n->idx == 0) { return; } printf("[%c", TRIE_INDEX2CHAR(n->idx)); for (i = 0; i < n->num_segments; i++) { printf("%c", n->segment[i]); } if (n == r) { printf("] (%d) %s\n", n->refcount, suffix); } else { printf("] "); } } static void trie_node_ref(struct trie *t, struct trie_node *node) { if (t->header == node) { return; } node->refcount++; } static void trie_node_deref(struct trie *t, struct trie_node *node) { if (!trie_node_alive(node)) { return; } node->refcount--; if (node->refcount > 0) { return; } trie_node_destroy(t, node); } static void trie_destroy(struct qb_map *map) { struct trie *t = (struct trie *)map; struct trie_node *cur_node = t->header; struct trie_node *fwd_node; do { fwd_node = trie_node_next(cur_node, t->header, QB_FALSE); trie_node_destroy(t, cur_node); } while ((cur_node = fwd_node)); free(t); } static struct trie_node * trie_new_node(struct trie *t, struct trie_node *parent) { struct trie_node *new_node = calloc(1, sizeof(struct trie_node)); if (new_node == NULL) { return NULL; } new_node->parent = parent; new_node->num_children = 0; new_node->children = NULL; new_node->num_segments = 0; new_node->segment = NULL; t->num_nodes++; t->mem_used += sizeof(struct trie_node); qb_list_init(&new_node->notifier_head); return new_node; } void qb_trie_dump(qb_map_t* m) { struct trie * t = (struct trie*)m; struct trie_node *n; if (t == NULL) { return; } printf("nodes: %d, bytes: %d\n", t->num_nodes, t->mem_used); n = t->header; do { if (n->num_children == 0) { trie_print_node(n, n, " "); } n = trie_node_next(n, t->header, QB_FALSE); } while (n); } static void trie_put(struct qb_map *map, const char *key, const void *value) { struct trie *t = (struct trie *)map; struct trie_node *n = trie_insert(t, key); if (n) { const char *old_value = n->value; const char *old_key = n->key; n->key = (char *)key; n->value = (void *)value; if (old_value == NULL) { trie_node_ref(t, n); t->length++; trie_notify(n, QB_MAP_NOTIFY_INSERTED, n->key, NULL, n->value); } else { trie_notify(n, QB_MAP_NOTIFY_REPLACED, (char *)old_key, (void *)old_value, (void *)value); } } } static int32_t trie_rm(struct qb_map *map, const char *key) { struct trie *t = (struct trie *)map; struct trie_node *n = trie_lookup(t, key, QB_TRUE); if (n) { trie_node_deref(t, n); t->length--; return QB_TRUE; } else { return QB_FALSE; } } static void * trie_get(struct qb_map *map, const char *key) { struct trie *t = (struct trie *)map; struct trie_node *n = trie_lookup(t, key, QB_TRUE); if (n) { return n->value; } return NULL; } static void trie_notify_deref(struct qb_map_notifier *f) { f->refcount--; if (f->refcount == 0) { qb_list_del(&f->list); free(f); } } static void trie_notify_ref(struct qb_map_notifier *f) { f->refcount++; } static void trie_notify(struct trie_node *n, uint32_t event, const char *key, void *old_value, void *value) { struct trie_node *c = n; struct qb_list_head *list; + struct qb_list_head *next; struct qb_map_notifier *tn; do { - for (list = c->notifier_head.next; - list != &c->notifier_head; ) { + qb_list_for_each_safe(list, next, &c->notifier_head) { tn = qb_list_entry(list, struct qb_map_notifier, list); trie_notify_ref(tn); if ((tn->events & event) && ((tn->events & QB_MAP_NOTIFY_RECURSIVE) || (n == c))) { tn->callback(event, (char *)key, old_value, value, tn->user_data); } if (((event & QB_MAP_NOTIFY_DELETED) || (event & QB_MAP_NOTIFY_REPLACED)) && (tn->events & QB_MAP_NOTIFY_FREE)) { tn->callback(QB_MAP_NOTIFY_FREE, (char *)key, old_value, value, tn->user_data); } - list = list->next; trie_notify_deref(tn); } c = c->parent; } while (c); } static int32_t trie_notify_add(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, void *user_data) { struct trie *t = (struct trie *)m; struct qb_map_notifier *f; struct trie_node *n; struct qb_list_head *list; int add_to_tail = QB_FALSE; if (key) { n = trie_lookup(t, key, QB_TRUE); if (n == NULL) { n = trie_insert(t, key); } } else { n = t->header; } if (n) { - for (list = n->notifier_head.next; - list != &n->notifier_head; list = list->next) { + qb_list_for_each(list, &n->notifier_head) { f = qb_list_entry(list, struct qb_map_notifier, list); if (events & QB_MAP_NOTIFY_FREE && f->events == events) { /* only one free notifier */ return -EEXIST; } if (f->events == events && f->callback == fn && f->user_data == user_data) { return -EEXIST; } } f = malloc(sizeof(struct qb_map_notifier)); if (f == NULL) { return -errno; } f->events = events; f->user_data = user_data; f->callback = fn; f->refcount = 1; qb_list_init(&f->list); if (key) { if (events & QB_MAP_NOTIFY_RECURSIVE) { add_to_tail = QB_TRUE; } } else { if (events & QB_MAP_NOTIFY_FREE) { add_to_tail = QB_TRUE; } } if (add_to_tail) { qb_list_add_tail(&f->list, &n->notifier_head); } else { qb_list_add(&f->list, &n->notifier_head); } return 0; } return -EINVAL; } static int32_t trie_notify_del(qb_map_t * m, const char *key, qb_map_notify_fn fn, int32_t events, int32_t cmp_userdata, void *user_data) { struct trie *t = (struct trie *)m; struct qb_map_notifier *f; struct trie_node *n; struct qb_list_head *list; + struct qb_list_head *next; int32_t found = QB_FALSE; if (key) { n = trie_lookup(t, key, QB_FALSE); } else { n = t->header; } if (n == NULL) { return -ENOENT; } - for (list = n->notifier_head.next; - list != &n->notifier_head; ) { + qb_list_for_each_safe(list, next, &n->notifier_head) { f = qb_list_entry(list, struct qb_map_notifier, list); trie_notify_ref(f); if (f->events == events && f->callback == fn) { if (cmp_userdata && (f->user_data == user_data)) { trie_notify_deref(f); found = QB_TRUE; } else if (!cmp_userdata) { trie_notify_deref(f); found = QB_TRUE; } } - list = list->next; trie_notify_deref(f); } if (found) { trie_node_release(t, n); return 0; } else { return -ENOENT; } } static qb_map_iter_t * trie_iter_create(struct qb_map *map, const char *prefix) { struct trie_iter *i = malloc(sizeof(struct trie_iter)); struct trie *t = (struct trie *)map; if (i == NULL) { return NULL; } i->i.m = map; i->prefix = prefix; i->n = t->header; i->root = t->header; return (qb_map_iter_t *) i; } static const char * trie_iter_next(qb_map_iter_t * i, void **value) { struct trie_iter *si = (struct trie_iter *)i; struct trie_node *p = si->n; struct trie *t = (struct trie *)(i->m); if (p == NULL) { return NULL; } if (p->parent == NULL && si->prefix) { si->root = trie_lookup(t, si->prefix, QB_FALSE); if (si->root == NULL) { si->n = NULL; } else if (si->root->value == NULL) { si->n = trie_node_next(si->root, si->root, QB_FALSE); } else { si->n = si->root; } } else { si->n = trie_node_next(p, si->root, QB_FALSE); } if (si->n == NULL) { trie_node_deref(t, p); return NULL; } trie_node_ref(t, si->n); trie_node_deref(t, p); *value = si->n->value; return si->n->key; } static void trie_iter_free(qb_map_iter_t * i) { struct trie_iter *si = (struct trie_iter *)i; struct trie *t = (struct trie *)(i->m); if (si->n != NULL) { /* if free'ing the iterator before getting to the last * node make sure we de-ref the current node. */ trie_node_deref(t, si->n); } free(i); } static size_t trie_count_get(struct qb_map *map) { struct trie *list = (struct trie *)map; return list->length; } qb_map_t * qb_trie_create(void) { struct trie *t = malloc(sizeof(struct trie)); if (t == NULL) { return NULL; } t->map.put = trie_put; t->map.get = trie_get; t->map.rm = trie_rm; t->map.count_get = trie_count_get; t->map.iter_create = trie_iter_create; t->map.iter_next = trie_iter_next; t->map.iter_free = trie_iter_free; t->map.destroy = trie_destroy; t->map.notify_add = trie_notify_add; t->map.notify_del = trie_notify_del; t->length = 0; t->num_nodes = 0; t->mem_used = sizeof(struct trie); t->header = trie_new_node(t, NULL); return (qb_map_t *) t; }