From 21f556518d86641f91344e1509c811e1fae65003 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Fri, 3 Feb 2006 14:57:47 +0100 Subject: [PATCH] [PATCH] blktrace: Make the subbuf adding/removing lockless --- barrier.h | 16 +++++++ blktrace.c | 63 ++++++++++++++++--------- list.h | 134 ----------------------------------------------------- 3 files changed, 57 insertions(+), 156 deletions(-) create mode 100644 barrier.h delete mode 100644 list.h diff --git a/barrier.h b/barrier.h new file mode 100644 index 0000000..5f420d1 --- /dev/null +++ b/barrier.h @@ -0,0 +1,16 @@ +#ifndef BARRIER_H +#define BARRIER_H + +#if defined(__ia64__) +#define store_barrier() asm volatile ("mf" ::: "memory") +#elif defined(__x86_64__) +#define store_barrier() asm volatile("sfence" ::: "memory") +#elif defined(__i386__) +#define store_barrier() asm volatile ("": : :"memory") +#elif defined(__ppc__) || defined(__powerpc__) +#define store_barrier() asm volatile ("eieio" : : : "memory") +#else +#error Define store_barrier() for your CPU +#endif + +#endif diff --git a/blktrace.c b/blktrace.c index 8601194..0054b87 100644 --- a/blktrace.c +++ b/blktrace.c @@ -39,7 +39,7 @@ #include #include "blktrace.h" -#include "list.h" +#include "barrier.h" static char blktrace_version[] = "0.99"; @@ -131,12 +131,20 @@ static struct option l_opts[] = { }; struct tip_subbuf { - struct list_head list; void *buf; unsigned int len; unsigned int max_len; }; +#define FIFO_SIZE (1024) /* should be plenty big! */ +#define CL_SIZE (128) /* cache line, any bigger? */ + +struct tip_subbuf_fifo { + int tail __attribute__((aligned(CL_SIZE))); + int head __attribute__((aligned(CL_SIZE))); + struct tip_subbuf *q[FIFO_SIZE]; +}; + struct thread_information { int cpu; pthread_t thread; @@ -157,8 +165,7 @@ struct thread_information { int exited; - pthread_mutex_t lock; - struct list_head subbuf_list; + struct tip_subbuf_fifo fifo; struct tip_subbuf *leftover_ts; }; @@ -319,14 +326,37 @@ static int read_data(struct thread_information *tip, void *buf, int len) return ret; } -static inline void tip_fd_unlock(struct thread_information *tip) +static inline struct tip_subbuf *subbuf_fifo_dequeue(struct thread_information *tip) { - pthread_mutex_unlock(&tip->lock); + const int head = tip->fifo.head; + const int next = (head + 1) & (FIFO_SIZE - 1); + + if (head != tip->fifo.tail) { + struct tip_subbuf *ts = tip->fifo.q[head]; + + store_barrier(); + tip->fifo.head = next; + return ts; + } + + return NULL; } -static inline void tip_fd_lock(struct thread_information *tip) +static inline int subbuf_fifo_queue(struct thread_information *tip, + struct tip_subbuf *ts) { - pthread_mutex_lock(&tip->lock); + const int tail = tip->fifo.tail; + const int next = (tail + 1) & (FIFO_SIZE - 1); + + if (next != tip->fifo.head) { + tip->fifo.q[tail] = ts; + store_barrier(); + tip->fifo.tail = next; + return 0; + } + + fprintf(stderr, "fifo too small!\n"); + return 1; } static int get_subbuf(struct thread_information *tip) @@ -341,10 +371,7 @@ static int get_subbuf(struct thread_information *tip) ret = read_data(tip, ts->buf, ts->max_len); if (ret > 0) { ts->len = ret; - tip_fd_lock(tip); - list_add_tail(&ts->list, &tip->subbuf_list); - tip_fd_unlock(tip); - return 0; + return subbuf_fifo_queue(tip, ts); } free(ts->buf); @@ -494,14 +521,7 @@ static int flush_subbuf(struct thread_information *tip, struct tip_subbuf *ts) static int write_tip_events(struct thread_information *tip) { - struct tip_subbuf *ts = NULL; - - tip_fd_lock(tip); - if (!list_empty(&tip->subbuf_list)) { - ts = list_entry(tip->subbuf_list.next, struct tip_subbuf, list); - list_del(&ts->list); - } - tip_fd_unlock(tip); + struct tip_subbuf *ts = subbuf_fifo_dequeue(tip); if (ts) return flush_subbuf(tip, ts); @@ -562,8 +582,7 @@ static int start_threads(struct device_information *dip) tip->cpu = j; tip->device = dip; tip->events_processed = 0; - pthread_mutex_init(&tip->lock, NULL); - INIT_LIST_HEAD(&tip->subbuf_list); + memset(&tip->fifo, 0, sizeof(tip->fifo)); tip->leftover_ts = NULL; if (pipeline) { diff --git a/list.h b/list.h deleted file mode 100644 index cedbafa..0000000 --- a/list.h +++ /dev/null @@ -1,134 +0,0 @@ -#ifndef _LINUX_LIST_H -#define _LINUX_LIST_H - -#undef offsetof -#ifdef __compiler_offsetof -#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) -#else -#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) -#endif - -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) - -/* - * Simple doubly linked list implementation. - * - * Some of the internal functions ("__xxx") are useful when - * manipulating whole lists rather than single entries, as - * sometimes we already know the next/prev entries and we can - * generate better code by using them directly rather than - * using the generic single-entry routines. - */ - -struct list_head { - struct list_head *next, *prev; -}; - -#define LIST_HEAD_INIT(name) { &(name), &(name) } - -#define LIST_HEAD(name) \ - struct list_head name = LIST_HEAD_INIT(name) - -#define INIT_LIST_HEAD(ptr) do { \ - (ptr)->next = (ptr); (ptr)->prev = (ptr); \ -} while (0) - -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_add(struct list_head *new, - struct list_head *prev, - struct list_head *next) -{ - next->prev = new; - new->next = next; - new->prev = prev; - prev->next = new; -} - -/** - * list_add - add a new entry - * @new: new entry to be added - * @head: list head to add it after - * - * Insert a new entry after the specified head. - * This is good for implementing stacks. - */ -static inline void list_add(struct list_head *new, struct list_head *head) -{ - __list_add(new, head, head->next); -} - -static inline void list_add_tail(struct list_head *new, struct list_head *head) -{ - __list_add(new, head->prev, head); -} - -/* - * Delete a list entry by making the prev/next entries - * point to each other. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_del(struct list_head * prev, struct list_head * next) -{ - next->prev = prev; - prev->next = next; -} - -/** - * list_del - deletes entry from list. - * @entry: the element to delete from the list. - * Note: list_empty on entry does not return true after this, the entry is - * in an undefined state. - */ -static inline void list_del(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - entry->next = NULL; - entry->prev = NULL; -} - -/** - * list_empty - tests whether a list is empty - * @head: the list to test. - */ -static inline int list_empty(const struct list_head *head) -{ - return head->next == head; -} - -/** - * list_entry - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - */ -#define list_entry(ptr, type, member) \ - container_of(ptr, type, member) - -/** - * list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. - */ -#define list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) - -/** - * list_for_each_safe - iterate over a list safe against removal of list entry - * @pos: the &struct list_head to use as a loop counter. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_safe(pos, n, head) \ - for (pos = (head)->next, n = pos->next; pos != (head); \ - pos = n, n = pos->next) - -#endif -- 2.25.1