diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 24 | ||||
| -rw-r--r-- | lib/Makefile | 6 | ||||
| -rw-r--r-- | lib/average.c | 61 | ||||
| -rw-r--r-- | lib/hexdump.c | 16 | ||||
| -rw-r--r-- | lib/ioq.c | 304 | ||||
| -rw-r--r-- | lib/kref.c | 30 | ||||
| -rw-r--r-- | lib/nlattr.c | 24 | ||||
| -rw-r--r-- | lib/shm_signal.c | 196 | ||||
| -rw-r--r-- | lib/swiotlb.c | 2 | ||||
| -rw-r--r-- | lib/timerlist.c | 118 |
10 files changed, 767 insertions, 14 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index fa9bf2c06199..3d498b298163 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -210,4 +210,28 @@ config GENERIC_ATOMIC64 config LRU_CACHE tristate +config AVERAGE + bool + +config SHM_SIGNAL + tristate "SHM Signal - Generic shared-memory signaling mechanism" + default n + help + Provides a shared-memory based signaling mechanism to indicate + memory-dirty notifications between two end-points. + + If unsure, say N + +config IOQ + tristate "IO-Queue library - Generic shared-memory queue" + select SHM_SIGNAL + default n + help + IOQ is a generic shared-memory-queue mechanism that happens to be + friendly to virtualization boundaries. It can be used in a variety + of ways, though its intended purpose is to become a low-level + communication path for paravirtualized drivers. + + If unsure, say N + endmenu diff --git a/lib/Makefile b/lib/Makefile index e6a3763b8212..48cca7674a0e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o \ + rbtree.o radix-tree.o dump_stack.o timerlist.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ @@ -82,6 +82,8 @@ obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o obj-$(CONFIG_SMP) += percpu_counter.o obj-$(CONFIG_AUDIT_GENERIC) += audit.o +obj-$(CONFIG_SHM_SIGNAL) += shm_signal.o +obj-$(CONFIG_IOQ) += ioq.o obj-$(CONFIG_SWIOTLB) += swiotlb.o obj-$(CONFIG_IOMMU_HELPER) += iommu-helper.o @@ -106,6 +108,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o +obj-$(CONFIG_AVERAGE) += average.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/average.c b/lib/average.c new file mode 100644 index 000000000000..5576c2841496 --- /dev/null +++ b/lib/average.c @@ -0,0 +1,61 @@ +/* + * lib/average.c + * + * This source code is licensed under the GNU General Public License, + * Version 2. See the file COPYING for more details. + */ + +#include <linux/module.h> +#include <linux/average.h> +#include <linux/bug.h> +#include <linux/log2.h> + +/** + * DOC: Exponentially Weighted Moving Average (EWMA) + * + * These are generic functions for calculating Exponentially Weighted Moving + * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled + * up internal representation of the average value to prevent rounding errors. + * The factor for scaling up and the exponential weight (or decay rate) have to + * be specified thru the init fuction. The structure should not be accessed + * directly but only thru the helper functions. + */ + +/** + * ewma_init() - Initialize EWMA parameters + * @avg: Average structure + * @factor: Factor to use for the scaled up internal value. The maximum value + * of averages can be ULONG_MAX/(factor*weight). For performance reasons + * factor has to be a power of 2. + * @weight: Exponential weight, or decay rate. This defines how fast the + * influence of older values decreases. For performance reasons weight has + * to be a power of 2. + * + * Initialize the EWMA parameters for a given struct ewma @avg. + */ +void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight) +{ + WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor)); + + avg->weight = ilog2(weight); + avg->factor = ilog2(factor); + avg->internal = 0; +} +EXPORT_SYMBOL(ewma_init); + +/** + * ewma_add() - Exponentially weighted moving average (EWMA) + * @avg: Average structure + * @val: Current value + * + * Add a sample to the average. + */ +struct ewma *ewma_add(struct ewma *avg, unsigned long val) +{ + avg->internal = avg->internal ? + (((avg->internal << avg->weight) - avg->internal) + + (val << avg->factor)) >> avg->weight : + (val << avg->factor); + return avg; +} +EXPORT_SYMBOL(ewma_add); diff --git a/lib/hexdump.c b/lib/hexdump.c index 5d7a4802c562..b66b2bd67952 100644 --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -34,6 +34,22 @@ int hex_to_bin(char ch) EXPORT_SYMBOL(hex_to_bin); /** + * hex2bin - convert an ascii hexadecimal string to its binary representation + * @dst: binary result + * @src: ascii hexadecimal string + * @count: result length + */ +void hex2bin(u8 *dst, const char *src, size_t count) +{ + while (count--) { + *dst = hex_to_bin(*src++) << 4; + *dst += hex_to_bin(*src++); + dst++; + } +} +EXPORT_SYMBOL(hex2bin); + +/** * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory * @buf: data blob to dump * @len: number of bytes in the @buf diff --git a/lib/ioq.c b/lib/ioq.c new file mode 100644 index 000000000000..4027848d7436 --- /dev/null +++ b/lib/ioq.c @@ -0,0 +1,304 @@ +/* + * Copyright 2009 Novell. All Rights Reserved. + * + * See include/linux/ioq.h for documentation + * + * Author: + * Gregory Haskins <ghaskins@novell.com> + * + * This file is free software; you can redistribute it and/or modify + * it under the terms of version 2 of the GNU General Public License + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include <linux/sched.h> +#include <linux/ioq.h> +#include <linux/bitops.h> +#include <linux/module.h> + +MODULE_AUTHOR("Gregory Haskins"); +MODULE_LICENSE("GPL"); +MODULE_VERSION("1"); + +#ifndef NULL +#define NULL 0 +#endif + +static int ioq_iter_setpos(struct ioq_iterator *iter, u32 pos) +{ + struct ioq *ioq = iter->ioq; + + BUG_ON(pos >= ioq->count); + + iter->pos = pos; + iter->desc = &ioq->ring[pos]; + + return 0; +} + +static inline u32 modulo_inc(u32 val, u32 mod) +{ + BUG_ON(val >= mod); + + if (val == (mod - 1)) + return 0; + + return val + 1; +} + +static inline int idx_full(struct ioq_ring_idx *idx) +{ + return idx->full && (idx->head == idx->tail); +} + +int ioq_iter_seek(struct ioq_iterator *iter, enum ioq_seek_type type, + long offset, int flags) +{ + struct ioq_ring_idx *idx = iter->idx; + u32 pos; + + switch (type) { + case ioq_seek_next: + pos = modulo_inc(iter->pos, iter->ioq->count); + break; + case ioq_seek_tail: + pos = le32_to_cpu(idx->tail); + break; + case ioq_seek_head: + pos = le32_to_cpu(idx->head); + break; + case ioq_seek_set: + if (offset >= iter->ioq->count) + return -1; + pos = offset; + break; + default: + return -EINVAL; + } + + return ioq_iter_setpos(iter, pos); +} +EXPORT_SYMBOL_GPL(ioq_iter_seek); + +static int ioq_ring_count(struct ioq_ring_idx *idx, int count) +{ + u32 head = le32_to_cpu(idx->head); + u32 tail = le32_to_cpu(idx->tail); + + if (idx->full && (head == tail)) + return count; + else if (tail >= head) + return tail - head; + else + return (tail + count) - head; +} + +static void idx_tail_push(struct ioq_ring_idx *idx, int count) +{ + u32 tail = modulo_inc(le32_to_cpu(idx->tail), count); + u32 head = le32_to_cpu(idx->head); + + if (head == tail) { + rmb(); + + /* + * Setting full here may look racy, but note that we havent + * flipped the owner bit yet. So it is impossible for the + * remote locale to move head in such a way that this operation + * becomes invalid + */ + idx->full = 1; + wmb(); + } + + idx->tail = cpu_to_le32(tail); +} + +int ioq_iter_push(struct ioq_iterator *iter, int flags) +{ + struct ioq_ring_head *head_desc = iter->ioq->head_desc; + struct ioq_ring_idx *idx = iter->idx; + int ret; + + /* + * Its only valid to push if we are currently pointed at the tail + */ + if (iter->pos != le32_to_cpu(idx->tail) || iter->desc->sown != iter->ioq->locale) + return -EINVAL; + + idx_tail_push(idx, iter->ioq->count); + if (iter->dualidx) { + idx_tail_push(&head_desc->idx[ioq_idxtype_inuse], + iter->ioq->count); + if (head_desc->idx[ioq_idxtype_inuse].tail != + head_desc->idx[ioq_idxtype_valid].tail) { + SHM_SIGNAL_FAULT(iter->ioq->signal, + "Tails not synchronized"); + return -EINVAL; + } + } + + wmb(); /* the index must be visible before the sown, or signal */ + + if (iter->flipowner) { + iter->desc->sown = !iter->ioq->locale; + wmb(); /* sown must be visible before we signal */ + } + + ret = ioq_iter_seek(iter, ioq_seek_next, 0, flags); + + if (iter->update) + ioq_signal(iter->ioq, 0); + + return ret; +} +EXPORT_SYMBOL_GPL(ioq_iter_push); + +int ioq_iter_pop(struct ioq_iterator *iter, int flags) +{ + struct ioq_ring_idx *idx = iter->idx; + int ret; + + /* + * Its only valid to pop if we are currently pointed at the head + */ + if (iter->pos != le32_to_cpu(idx->head) || iter->desc->sown != iter->ioq->locale) + return -EINVAL; + + idx->head = cpu_to_le32(modulo_inc(le32_to_cpu(idx->head), iter->ioq->count)); + wmb(); /* head must be visible before full */ + + if (idx->full) { + idx->full = 0; + wmb(); /* full must be visible before sown */ + } + + if (iter->flipowner) { + iter->desc->sown = !iter->ioq->locale; + wmb(); /* sown must be visible before we signal */ + } + + ret = ioq_iter_seek(iter, ioq_seek_next, 0, flags); + + if (iter->update) + ioq_signal(iter->ioq, 0); + + return ret; +} +EXPORT_SYMBOL_GPL(ioq_iter_pop); + +static struct ioq_ring_idx *idxtype_to_idx(struct ioq *ioq, + enum ioq_idx_type type) +{ + struct ioq_ring_idx *idx; + + switch (type) { + case ioq_idxtype_valid: + case ioq_idxtype_inuse: + idx = &ioq->head_desc->idx[type]; + break; + default: + panic("IOQ: illegal index type: %d", type); + break; + } + + return idx; +} + +int ioq_iter_init(struct ioq *ioq, struct ioq_iterator *iter, + enum ioq_idx_type type, int flags) +{ + iter->ioq = ioq; + iter->update = (flags & IOQ_ITER_AUTOUPDATE); + iter->flipowner = !(flags & IOQ_ITER_NOFLIPOWNER); + iter->pos = -1; + iter->desc = NULL; + iter->dualidx = 0; + + if (type == ioq_idxtype_both) { + /* + * "both" is a special case, so we set the dualidx flag. + * + * However, we also just want to use the valid-index + * for normal processing, so override that here + */ + type = ioq_idxtype_valid; + iter->dualidx = 1; + } + + iter->idx = idxtype_to_idx(ioq, type); + + return 0; +} +EXPORT_SYMBOL_GPL(ioq_iter_init); + +int ioq_count(struct ioq *ioq, enum ioq_idx_type type) +{ + return ioq_ring_count(idxtype_to_idx(ioq, type), ioq->count); +} +EXPORT_SYMBOL_GPL(ioq_count); + +int ioq_remain(struct ioq *ioq, enum ioq_idx_type type) +{ + int count = ioq_ring_count(idxtype_to_idx(ioq, type), ioq->count); + + return ioq->count - count; +} +EXPORT_SYMBOL_GPL(ioq_remain); + +int ioq_size(struct ioq *ioq) +{ + return ioq->count; +} +EXPORT_SYMBOL_GPL(ioq_size); + +int ioq_full(struct ioq *ioq, enum ioq_idx_type type) +{ + struct ioq_ring_idx *idx = idxtype_to_idx(ioq, type); + + return idx_full(idx); +} +EXPORT_SYMBOL_GPL(ioq_full); + +static void ioq_shm_signal(struct shm_signal_notifier *notifier) +{ + struct ioq *ioq = container_of(notifier, struct ioq, shm_notifier); + + if (waitqueue_active(&ioq->wq)) + wake_up(&ioq->wq); + + if (ioq->notifier) + ioq->notifier->signal(ioq->notifier); +} + +void ioq_init(struct ioq *ioq, + struct ioq_ops *ops, + enum ioq_locality locale, + struct ioq_ring_head *head, + struct shm_signal *signal, + size_t count) +{ + memset(ioq, 0, sizeof(*ioq)); + kref_init(&ioq->kref); + init_waitqueue_head(&ioq->wq); + + ioq->ops = ops; + ioq->locale = locale; + ioq->head_desc = head; + ioq->ring = &head->ring[0]; + ioq->count = count; + ioq->signal = signal; + + ioq->shm_notifier.signal = &ioq_shm_signal; + signal->notifier = &ioq->shm_notifier; +} +EXPORT_SYMBOL_GPL(ioq_init); diff --git a/lib/kref.c b/lib/kref.c index d3d227a08a4b..3efb882b11db 100644 --- a/lib/kref.c +++ b/lib/kref.c @@ -62,6 +62,36 @@ int kref_put(struct kref *kref, void (*release)(struct kref *kref)) return 0; } + +/** + * kref_sub - subtract a number of refcounts for object. + * @kref: object. + * @count: Number of recounts to subtract. + * @release: pointer to the function that will clean up the object when the + * last reference to the object is released. + * This pointer is required, and it is not acceptable to pass kfree + * in as this function. + * + * Subtract @count from the refcount, and if 0, call release(). + * Return 1 if the object was removed, otherwise return 0. Beware, if this + * function returns 0, you still can not count on the kref from remaining in + * memory. Only use the return value if you want to see if the kref is now + * gone, not present. + */ +int kref_sub(struct kref *kref, unsigned int count, + void (*release)(struct kref *kref)) +{ + WARN_ON(release == NULL); + WARN_ON(release == (void (*)(struct kref *))kfree); + + if (atomic_sub_and_test((int) count, &kref->refcount)) { + release(kref); + return 1; + } + return 0; +} + EXPORT_SYMBOL(kref_init); EXPORT_SYMBOL(kref_get); EXPORT_SYMBOL(kref_put); +EXPORT_SYMBOL(kref_sub); diff --git a/lib/nlattr.c b/lib/nlattr.c index c4706eb98d3d..5021cbc34411 100644 --- a/lib/nlattr.c +++ b/lib/nlattr.c @@ -15,7 +15,7 @@ #include <linux/types.h> #include <net/netlink.h> -static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = { +static const u16 nla_attr_minlen[NLA_TYPE_MAX+1] = { [NLA_U8] = sizeof(u8), [NLA_U16] = sizeof(u16), [NLA_U32] = sizeof(u32), @@ -23,7 +23,7 @@ static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = { [NLA_NESTED] = NLA_HDRLEN, }; -static int validate_nla(struct nlattr *nla, int maxtype, +static int validate_nla(const struct nlattr *nla, int maxtype, const struct nla_policy *policy) { const struct nla_policy *pt; @@ -115,10 +115,10 @@ static int validate_nla(struct nlattr *nla, int maxtype, * * Returns 0 on success or a negative error code. */ -int nla_validate(struct nlattr *head, int len, int maxtype, +int nla_validate(const struct nlattr *head, int len, int maxtype, const struct nla_policy *policy) { - struct nlattr *nla; + const struct nlattr *nla; int rem, err; nla_for_each_attr(nla, head, len, rem) { @@ -167,16 +167,16 @@ nla_policy_len(const struct nla_policy *p, int n) * @policy: validation policy * * Parses a stream of attributes and stores a pointer to each attribute in - * the tb array accessable via the attribute type. Attributes with a type + * the tb array accessible via the attribute type. Attributes with a type * exceeding maxtype will be silently ignored for backwards compatibility * reasons. policy may be set to NULL if no validation is required. * * Returns 0 on success or a negative error code. */ -int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len, - const struct nla_policy *policy) +int nla_parse(struct nlattr **tb, int maxtype, const struct nlattr *head, + int len, const struct nla_policy *policy) { - struct nlattr *nla; + const struct nlattr *nla; int rem, err; memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1)); @@ -191,7 +191,7 @@ int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len, goto errout; } - tb[type] = nla; + tb[type] = (struct nlattr *)nla; } } @@ -212,14 +212,14 @@ errout: * * Returns the first attribute in the stream matching the specified type. */ -struct nlattr *nla_find(struct nlattr *head, int len, int attrtype) +struct nlattr *nla_find(const struct nlattr *head, int len, int attrtype) { - struct nlattr *nla; + const struct nlattr *nla; int rem; nla_for_each_attr(nla, head, len, rem) if (nla_type(nla) == attrtype) - return nla; + return (struct nlattr *)nla; return NULL; } diff --git a/lib/shm_signal.c b/lib/shm_signal.c new file mode 100644 index 000000000000..8d3e9b418a27 --- /dev/null +++ b/lib/shm_signal.c @@ -0,0 +1,196 @@ +/* + * Copyright 2009 Novell. All Rights Reserved. + * + * See include/linux/shm_signal.h for documentation + * + * Author: + * Gregory Haskins <ghaskins@novell.com> + * + * This file is free software; you can redistribute it and/or modify + * it under the terms of version 2 of the GNU General Public License + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/shm_signal.h> + +MODULE_AUTHOR("Gregory Haskins"); +MODULE_LICENSE("GPL"); +MODULE_VERSION("1"); + +int shm_signal_enable(struct shm_signal *s, int flags) +{ + struct shm_signal_irq *irq = &s->desc->irq[s->locale]; + unsigned long iflags; + + spin_lock_irqsave(&s->lock, iflags); + + irq->enabled = 1; + wmb(); + + if ((irq->dirty || irq->pending) + && !test_bit(shm_signal_in_wakeup, &s->flags)) { + rmb(); + tasklet_schedule(&s->deferred_notify); + } + + spin_unlock_irqrestore(&s->lock, iflags); + + return 0; +} +EXPORT_SYMBOL_GPL(shm_signal_enable); + +int shm_signal_disable(struct shm_signal *s, int flags) +{ + struct shm_signal_irq *irq = &s->desc->irq[s->locale]; + + irq->enabled = 0; + wmb(); + + return 0; +} +EXPORT_SYMBOL_GPL(shm_signal_disable); + +/* + * signaling protocol: + * + * each side of the shm_signal has an "irq" structure with the following + * fields: + * + * - enabled: controlled by shm_signal_enable/disable() to mask/unmask + * the notification locally + * - dirty: indicates if the shared-memory is dirty or clean. This + * is updated regardless of the enabled/pending state so that + * the state is always accurately tracked. + * - pending: indicates if a signal is pending to the remote locale. + * This allows us to determine if a remote-notification is + * already in flight to optimize spurious notifications away. + */ +int shm_signal_inject(struct shm_signal *s, int flags) +{ + /* Load the irq structure from the other locale */ + struct shm_signal_irq *irq = &s->desc->irq[!s->locale]; + + /* + * We always mark the remote side as dirty regardless of whether + * they need to be notified. + */ + irq->dirty = 1; + wmb(); /* dirty must be visible before we test the pending state */ + + if (irq->enabled && !irq->pending) { + rmb(); + + /* + * If the remote side has enabled notifications, and we do + * not see a notification pending, we must inject a new one. + */ + irq->pending = 1; + wmb(); /* make it visible before we do the injection */ + + s->ops->inject(s); + } + + return 0; +} +EXPORT_SYMBOL_GPL(shm_signal_inject); + +void _shm_signal_wakeup(struct shm_signal *s) +{ + struct shm_signal_irq *irq = &s->desc->irq[s->locale]; + int dirty; + unsigned long flags; + + spin_lock_irqsave(&s->lock, flags); + + __set_bit(shm_signal_in_wakeup, &s->flags); + + /* + * The outer loop protects against race conditions between + * irq->dirty and irq->pending updates + */ + while (irq->enabled && (irq->dirty || irq->pending)) { + + /* + * Run until we completely exhaust irq->dirty (it may + * be re-dirtied by the remote side while we are in the + * callback). We let "pending" remain untouched until we have + * processed them all so that the remote side knows we do not + * need a new notification (yet). + */ + do { + irq->dirty = 0; + /* the unlock is an implicit wmb() for dirty = 0 */ + spin_unlock_irqrestore(&s->lock, flags); + + if (s->notifier) + s->notifier->signal(s->notifier); + + spin_lock_irqsave(&s->lock, flags); + dirty = irq->dirty; + rmb(); + + } while (irq->enabled && dirty); + + barrier(); + + /* + * We can finally acknowledge the notification by clearing + * "pending" after all of the dirty memory has been processed + * Races against this clearing are handled by the outer loop. + * Subsequent iterations of this loop will execute with + * pending=0 potentially leading to future spurious + * notifications, but this is an acceptable tradeoff as this + * will be rare and harmless. + */ + irq->pending = 0; + wmb(); + + } + + __clear_bit(shm_signal_in_wakeup, &s->flags); + spin_unlock_irqrestore(&s->lock, flags); + +} +EXPORT_SYMBOL_GPL(_shm_signal_wakeup); + +void _shm_signal_release(struct kref *kref) +{ + struct shm_signal *s = container_of(kref, struct shm_signal, kref); + + s->ops->release(s); +} +EXPORT_SYMBOL_GPL(_shm_signal_release); + +static void +deferred_notify(unsigned long data) +{ + struct shm_signal *s = (struct shm_signal *)data; + + _shm_signal_wakeup(s); +} + +void shm_signal_init(struct shm_signal *s, enum shm_signal_locality locale, + struct shm_signal_ops *ops, struct shm_signal_desc *desc) +{ + memset(s, 0, sizeof(*s)); + kref_init(&s->kref); + spin_lock_init(&s->lock); + tasklet_init(&s->deferred_notify, + deferred_notify, + (unsigned long)s); + s->locale = locale; + s->ops = ops; + s->desc = desc; +} +EXPORT_SYMBOL_GPL(shm_signal_init); diff --git a/lib/swiotlb.c b/lib/swiotlb.c index 7c06ee51a29a..c47bbe11b804 100644 --- a/lib/swiotlb.c +++ b/lib/swiotlb.c @@ -60,7 +60,7 @@ int swiotlb_force; static char *io_tlb_start, *io_tlb_end; /* - * The number of IO TLB blocks (in groups of 64) betweeen io_tlb_start and + * The number of IO TLB blocks (in groups of 64) between io_tlb_start and * io_tlb_end. This is command line adjustable via setup_io_tlb_npages. */ static unsigned long io_tlb_nslabs; diff --git a/lib/timerlist.c b/lib/timerlist.c new file mode 100644 index 000000000000..9101b42fd13d --- /dev/null +++ b/lib/timerlist.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-list + * + * Manages a simple list of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <linux/timerlist.h> +#include <linux/rbtree.h> + +/** + * timerlist_add - Adds timer to timerlist. + * + * @head: head of timerlist + * @node: timer node to be added + * + * Adds the timer node to the timerlist, sorted by the + * node's expires value. + */ +void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerlist_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerlist_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerlist_del - Removes a timer from the timerlist. + * + * @head: head of timerlist + * @node: timer node to be removed + * + * Removes the timer node from the timerlist. + */ +void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerlist_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerlist_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerlist + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerlist_node *timerlist_getnext(struct timerlist_head *head) +{ + return head->next; +} + + +/** + * timerlist_iterate_next - Returns the timer after the provided timer + * + * @node: Pointer to a timer. + * + * Provides the timer that is after the given node. This is used, when + * necessary, to iterate through the list of timers in a timer list + * without modifying the list. + */ +struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerlist_node, node); +} |