lkml.org 
[lkml]   [2004]   [Sep]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC, 2.6] a simple FIFO implementation
    Stelian Pop <stelian@popies.net> wrote:
    >
    > Hi all,
    >
    > Is there a reason there is no API implementing a simple in-kernel
    > FIFO ? A linked list is a bit overkill...
    >
    > +struct kfifo {
    > + unsigned int head;
    > + unsigned int tail;
    > + unsigned int size;
    > + unsigned int len;
    > + spinlock_t lock;
    > + unsigned char *buffer;
    > +};

    A circular buffer implementation needs only head and tail indices. `size'
    above appears to be redundant.

    Implementation-wise, the head and tail indices should *not* be constrained
    to be less than the size of the buffer. They should be allowed to wrap all
    the way back to zero. This allows you to distinguish between the
    completely-empty and completely-full states while using 100% of the storage.

    > +static inline struct kfifo *kfifo_alloc(unsigned int size) {

    This should not be inlined, and the caller should pass in the gfp_flags.

    > +static inline void kfifo_reset(struct kfifo *fifo) {

    uninline this.

    > + unsigned long flags;
    > +
    > + spin_lock_irqsave(&fifo->lock, flags);
    > +
    > + fifo->head = fifo->tail = 0;
    > + fifo->len = 0;
    > +
    > + spin_unlock_irqrestore(&fifo->lock, flags);
    > +}

    The caller should provide the locking. The spinlock should be removed.

    Or maybe provide a separate higher-level API which does the locking for
    you.

    > +static inline unsigned int kfifo_put(struct kfifo *fifo,
    > + unsigned char *buffer, unsigned int len) {
    > + unsigned long flags;
    > + unsigned int total, remaining;
    > +
    > + spin_lock_irqsave(&fifo->lock, flags);
    > +
    > + total = remaining = min(len, fifo->size - fifo->len);
    > + while (remaining > 0) {
    > + unsigned int l = min(remaining, fifo->size - fifo->tail);
    > + memcpy(fifo->buffer + fifo->tail, buffer, l);
    > + fifo->tail += l;
    > + fifo->tail %= fifo->size;
    > + fifo->len += l;
    > + buffer += l;
    > + remaining -= l;
    > + }
    > +
    > + spin_unlock_irqrestore(&fifo->lock, flags);
    > +
    > + return total;
    > +}

    This is too big to inline.

    > +static inline unsigned int kfifo_get(struct kfifo *fifo,
    > + unsigned char *buffer, unsigned int len) {
    > + unsigned long flags;
    > + unsigned int total, remaining;
    > +
    > + spin_lock_irqsave(&fifo->lock, flags);
    > +
    > + total = remaining = min(len, fifo->len);
    > + while (remaining > 0) {
    > + unsigned int l = min(remaining, fifo->size - fifo->head);
    > + memcpy(buffer, fifo->buffer + fifo->head, l);
    > + fifo->head += l;
    > + fifo->head %= fifo->size;
    > + fifo->len -= l;
    > + buffer += l;
    > + remaining -= l;
    > + }
    > +
    > + spin_unlock_irqrestore(&fifo->lock, flags);
    > +
    > + return total;

    whitespace damage

    > +}

    Too big to inline.

    > +/*
    > + * kfifo_len - returns the number of bytes available in the FIFO
    > + * @fifo: the fifo to be used.
    > + */
    > +static inline unsigned int kfifo_len(struct kfifo *fifo) {
    > + unsigned long flags;
    > + unsigned int result;
    > +
    > + spin_lock_irqsave(&fifo->lock, flags);
    > +
    > + result = fifo->len;
    > +
    > + spin_unlock_irqrestore(&fifo->lock, flags);
    > +
    > + return result;
    > +}

    And this.

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:06    [W:0.025 / U:0.572 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site