bdbuf.c

RTEMS (Real-Time Executive for Multiprocessor Systems) is a free open source real-time operating sys

/*
 * Disk I/O buffering
 * Buffer managment
 *
 * Copyright (C) 2001 OKTET Ltd., St.-Peterburg, Russia
 * Author: Andrey G. Ivanov <[e-mail]>
 *         Victor V. Vengerov <[e-mail]>
 *         Alexander Kukuta <[e-mail]>
 *
 * @(#) $Id: bdbuf.c,v 1.7 2003/01/03 16:39:46 joel Exp $
 */

#define __RTEMS_VIOLATE_KERNEL_VISIBILITY__
#include <rtems.h>
#include <limits.h>
#include <errno.h>
#include <assert.h>

#include "rtems/bdbuf.h"

/* Fatal errors: */
#define BLKDEV_FATAL_ERROR(n) (((unsigned32)'B' << 24) | ((unsigned32)(n) & (unsigned32)0x00FFFFFF))
#define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1)
#define BLKDEV_FATAL_BDBUF_SWAPOUT     BLKDEV_FATAL_ERROR(2)


#define SWAPOUT_PRIORITY 15
#define SWAPOUT_STACK_SIZE (RTEMS_MINIMUM_STACK_SIZE * 2)

static rtems_task bdbuf_swapout_task(rtems_task_argument unused);

/*
 * The groups of the blocks with the same size are collected in the
 * bd_pool. Note that a several of the buffer's groups with the
 * same size can exists.
 */
typedef struct bdbuf_pool
{
    bdbuf_buffer *tree;         /* Buffer descriptor lookup AVL tree root */

    Chain_Control free;         /* Free buffers list */
    Chain_Control lru;          /* Last recently used list */

    int           blksize;      /* The size of the blocks (in bytes) */
    int           nblks;        /* Number of blocks in this pool */
    rtems_id      bufget_sema;  /* Buffer obtain counting semaphore */
    void         *mallocd_bufs; /* Pointer to the malloc'd buffer memory,
                                   or NULL, if buffer memory provided in
                                   buffer configuration */
    bdbuf_buffer *bdbufs;       /* Pointer to table of buffer descriptors
                                   allocated for this buffer pool. */
} bdbuf_pool;

/* Buffering layer context definition */
struct bdbuf_context {
    bdbuf_pool    *pool;         /* Table of buffer pools */
    int            npools;       /* Number of entries in pool table */
    
    Chain_Control  mod;          /* Modified buffers list */
    rtems_id       flush_sema;   /* Buffer flush semaphore; counting 
                                    semaphore; incremented when buffer
                                    flushed to the disk; decremented when 
                                    buffer modified */
    rtems_id       swapout_task; /* Swapout task ID */
};

/* Block device request with a single buffer provided */
typedef struct blkdev_request1 {
    blkdev_request   req;
    blkdev_sg_buffer sg[1];
} blkdev_request1;

/* The static context of buffering layer */
static struct bdbuf_context bd_ctx;

#define SAFE
#ifdef SAFE
typedef rtems_mode preemption_key;

#define DISABLE_PREEMPTION(key) \
    do {                                                               \
        rtems_task_mode(RTEMS_NO_PREEMPT, RTEMS_PREEMPT_MASK, &(key)); \
    } while (0)

#define ENABLE_PREEMPTION(key) \
    do {                                                        \
        rtems_mode temp;                                        \
        rtems_task_mode((key), RTEMS_PREEMPT_MASK, &temp);      \
    } while (0)

#else
 
typedef boolean preemption_key;

#define DISABLE_PREEMPTION(key) \
    do {                                             \
        (key) = _Thread_Executing->is_preemptible;   \
        _Thread_Executing->is_preemptible = 0;       \
    } while (0)
    
#define ENABLE_PREEMPTION(key) \
    do {                                             \
        _Thread_Executing->is_preemptible = (key);   \
        if (_Thread_Evaluate_mode())                 \
            _Thread_Dispatch();                      \
    } while (0)

#endif


/* The default maximum height of 32 allows for AVL trees having
   between 5,704,880 and 4,294,967,295 nodes, depending on order of
   insertion.  You may change this compile-time constant as you
   wish. */
#ifndef AVL_MAX_HEIGHT
#define AVL_MAX_HEIGHT  32
#endif

/*
 * avl_search --
 *     Searches for the node with specified dev/block.
 *
 * PARAMETERS:
 *     root - pointer to the root node of the AVL-Tree.
 *     dev, block - search key
 *
 * RETURNS:
 *     NULL if node with specified dev/block not found
 *     non-NULL - pointer to the node with specified dev/block
 */
static bdbuf_buffer *
avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
{
    bdbuf_buffer *p = *root;

    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
    {
        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
        {
            p = p->avl.right;
        }
        else
        {
            p = p->avl.left;
        }
    }
    
    return p;
}


/* avl_search_for_sync --
 *     Search in AVL tree for first modified buffer belongs to specified
 *     disk device.
 *
 * PARAMETERS:
 *     root - pointer to tree root
 *     dd - disk device descriptor
 *
 * RETURNS:
 *     Block buffer, or NULL if no modified blocks on specified device
 *     exists.
 */
static bdbuf_buffer *
avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
{
    dev_t dev = dd->phys_dev->dev;
    blkdev_bnum block_start = dd->start;
    blkdev_bnum block_end = dd->start + dd->size - 1;

    bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT];
    bdbuf_buffer **buf_prev = buf_stack;
    bdbuf_buffer *p = *root;

    while (p != NULL)
    {
        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block_start)))
        {
            p = p->avl.right;
        }
        else if ((p->dev > dev) || ((p->dev == dev) && (p->block > block_end)))
        {
            p = p->avl.left;
        }
        else if (p->modified)
        {
            return p;
        }
        else
        {
            if (p->avl.right != NULL)
            {
                *buf_prev++ = p->avl.right;
            }
            p = p->avl.left;
        }

        if ((p == NULL) && (buf_prev > buf_stack))
        {
            p = *--buf_prev;
        }
    }

    return p;
}


/*
 * avl_insert --
 *     Inserts the specified node to the AVl-Tree.
 *
 * PARAMETERS:
 *     root - Pointer to pointer to the root node
 *     node - Pointer to the node to add.
 *
 * RETURNS:
 *     0 - The node added successfully
 *    -1 - An error occured
 */
static int
avl_insert(bdbuf_buffer **root, bdbuf_buffer *node)
{
    dev_t dev = node->dev;
    blkdev_bnum block = node->block;

    bdbuf_buffer *p = *root;
    bdbuf_buffer *q, *p1, *p2;
    bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT];
    bdbuf_buffer **buf_prev = buf_stack;

    boolean modified = FALSE;

    if (p == NULL)
    {
        *root = node;
        node->avl.left = NULL;
        node->avl.right = NULL;
        node->avl.bal = 0;
        return 0;
    }

    while (p != NULL)
    {
        *buf_prev++ = p;

        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
        {
            p->avl.cache = 1;
            q = p->avl.right;
            if (q == NULL)
            {
                q = node;
                p->avl.right = q = node;
                break;
            }
        }
        else if ((p->dev != dev) || (p->block != block))
        {
            p->avl.cache = -1;
            q = p->avl.left;
            if (q == NULL)
            {
                q = node;
                p->avl.left = q;
                break;
            }
        }
        else
        {
            return -1;
        }

        p = q;
    }

    q->avl.left = q->avl.right = NULL;
    q->avl.bal = 0;
    modified = TRUE;
    buf_prev--;

    while (modified)
    {
        if (p->avl.cache == -1)
        {
            switch (p->avl.bal)
            {
                case 1:
                    p->avl.bal = 0;
                    modified = FALSE;
                    break;

                case 0:
                    p->avl.bal = -1;
                    break;

                case -1:
                    p1 = p->avl.left;
                    if (p1->avl.bal == -1) /* simple LL-turn */
                    {
                        p->avl.left = p1->avl.right;
                        p1->avl.right = p;
                        p->avl.bal = 0;
                        p = p1;
                    }
                    else /* double LR-turn */
                    {
                        p2 = p1->avl.right;
                        p1->avl.right = p2->avl.left;
                        p2->avl.left = p1;
                        p->avl.left = p2->avl.right;
                        p2->avl.right = p;
                        if (p2->avl.bal == -1) p->avl.bal = +1; else p->avl.bal = 0;
                        if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0;
                        p = p2;
                    }
                    p->avl.bal = 0;
                    modified = FALSE;
                    break;

                default:
                    break;
            }
        }
        else
        {
            switch (p->avl.bal)
            {
                case -1:
                    p->avl.bal = 0;
                    modified = FALSE;
                    break;

                case 0:
                    p->avl.bal = 1;
                    break;

                case 1:
                    p1 = p->avl.right;
                    if (p1->avl.bal == 1) /* simple RR-turn */
                    {
                        p->avl.right = p1->avl.left;
                        p1->avl.left = p;
                        p->avl.bal = 0;
                        p = p1;
                    }
                    else /* double RL-turn */
                    {
                        p2 = p1->avl.left;
                        p1->avl.left = p2->avl.right;
                        p2->avl.right = p1;
                        p->avl.right = p2->avl.left;
                        p2->avl.left = p;
                        if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0;
                        if (p2->avl.bal == -1) p1->avl.bal = +1; else p1->avl.bal = 0;
                        p = p2;
                    }
                    p->avl.bal = 0;
                    modified = FALSE;
                    break;

                default:
                    break;
            }
        }
        q = p;
        if (buf_prev > buf_stack)
        {
            p = *--buf_prev;

            if (p->avl.cache == -1)
            {
                p->avl.left = q;
            }
            else
            {
                p->avl.right = q;
            }
        }
        else
        {
            *root = p;
            break;
        }
    };

    return 0;
}


/* avl_remove --
 *     removes the node from the tree.
 *
 * PARAMETERS:
 *     root_addr - Pointer to pointer to the root node
 *     node      - Pointer to the node to remove
 *
 * RETURNS:
 *     0 - Item removed
 *    -1 - No such item found
 */
static int
avl_remove(bdbuf_buffer **root, const bdbuf_buffer *node)
{
    dev_t dev = node->dev;
    blkdev_bnum block = node->block;

    bdbuf_buffer *p = *root;
    bdbuf_buffer *q, *r, *s, *p1, *p2;
    bdbuf_buffer *buf_stack[AVL_MAX_HEIGHT];
    bdbuf_buffer **buf_prev = buf_stack;

    boolean modified = FALSE;