source: rtems/cpukit/libblock/src/bdbuf.c @ e51bd96

4.104.114.84.95
Last change on this file since e51bd96 was e51bd96, checked in by Joel Sherrill <joel.sherrill@…>, on Feb 28, 2002 at 8:39:54 PM

2002-02-28 Joel Sherrill <joel@…>

  • Submitted by Victor V. Vengerov <vvv@…> and merged into the RTEMS source.
  • ChangeLog?, Makefile.am, README, configure.ac, include/Makefile.am, include/rtems/bdbuf.h, include/rtems/blkdev.h, include/rtems/diskdevs.h, include/rtems/ramdisk.h, include/rtems/.cvsignore, include/.cvsignore, src/Makefile.am, src/bdbuf.c, src/blkdev.c, src/diskdevs.c, src/ramdisk.c, src/.cvsignore, .cvsignore: New files.
  • Property mode set to 100644
File size: 51.2 KB
Line 
1/*
2 * Disk I/O buffering
3 * Buffer managment
4 *
5 * Copyright (C) 2001 OKTET Ltd., St.-Peterburg, Russia
6 * Author: Andrey G. Ivanov <Andrey.Ivanov@oktet.ru>
7 *         Victor V. Vengerov <vvv@oktet.ru>
8 *
9 * @(#) $Id$
10 */
11
12#define __RTEMS_VIOLATE_KERNEL_VISIBILITY__
13#include <rtems.h>
14#include <limits.h>
15#include <errno.h>
16#include <assert.h>
17
18#include "rtems/bdbuf.h"
19
20/* Fatal errors: */
21#define BLKDEV_FATAL_ERROR(n) (('B' << 24) | ((n) & 0x00FFFFFF))
22#define BLKDEV_FATAL_BDBUF_CONSISTENCY BLKDEV_FATAL_ERROR(1)
23#define BLKDEV_FATAL_BDBUF_SWAPOUT     BLKDEV_FATAL_ERROR(2)
24
25enum balance_factor {BF_LEFT = -1, 
26                     BF_NONE = 0, 
27                     BF_RIGHT = 1}; 
28
29
30#define SWAPOUT_PRIORITY 15
31#define SWAPOUT_STACK_SIZE (RTEMS_MINIMUM_STACK_SIZE * 2)
32
33static rtems_task bdbuf_swapout_task(rtems_task_argument unused);
34
35/*
36 * The groups of the blocks with the same size are collected in the
37 * bd_pool. Note that a several of the buffer's groups with the
38 * same size can exists.
39 */
40typedef struct bdbuf_pool
41{
42    bdbuf_buffer *tree;         /* Buffer descriptor lookup AVL tree root */
43
44    Chain_Control free;         /* Free buffers list */
45    Chain_Control lru;          /* Last recently used list */
46
47    int           blksize;      /* The size of the blocks (in bytes) */
48    int           nblks;        /* Number of blocks in this pool */
49    rtems_id      bufget_sema;  /* Buffer obtain counting semaphore */
50    void         *mallocd_bufs; /* Pointer to the malloc'd buffer memory,
51                                   or NULL, if buffer memory provided in
52                                   buffer configuration */
53    bdbuf_buffer *bdbufs;       /* Pointer to table of buffer descriptors
54                                   allocated for this buffer pool. */
55} bdbuf_pool;
56
57/* Buffering layer context definition */
58struct bdbuf_context {
59    bdbuf_pool    *pool;         /* Table of buffer pools */
60    int            npools;       /* Number of entries in pool table */
61   
62    Chain_Control  mod;          /* Modified buffers list */
63    rtems_id       flush_sema;   /* Buffer flush semaphore; counting
64                                    semaphore; incremented when buffer
65                                    flushed to the disk; decremented when
66                                    buffer modified */
67    rtems_id       swapout_task; /* Swapout task ID */
68};
69
70/* Block device request with a single buffer provided */
71typedef struct blkdev_request1 {
72    blkdev_request   req;
73    blkdev_sg_buffer sg[1];
74} blkdev_request1;
75
76/* The static context of buffering layer */
77static struct bdbuf_context bd_ctx;
78
79#define SAFE
80#ifdef SAFE
81typedef rtems_mode preemption_key;
82
83#define DISABLE_PREEMPTION(key) \
84    do {                                                               \
85        rtems_task_mode(RTEMS_PREEMPT_MASK, RTEMS_NO_PREEMPT, &(key)); \
86    } while (0)
87
88#define ENABLE_PREEMPTION(key) \
89    do {                                                        \
90        rtems_mode temp;                                        \
91        rtems_task_mode(RTEMS_PREEMPT_MASK, (key), &temp);      \
92    } while (0)
93
94#else
95 
96typedef boolean preemption_key;
97
98#define DISABLE_PREEMPTION(key) \
99    do {                                             \
100        (key) = _Thread_Executing->is_preemptible;   \
101        _Thread_Executing->is_preemptible = 0;       \
102    } while (0)
103   
104#define ENABLE_PREEMPTION(key) \
105    do {                                             \
106        _Thread_Executing->is_preemptible = (key);   \
107        if (_Thread_Evaluate_mode())                 \
108            _Thread_Dispatch();                      \
109    } while (0)
110
111#endif
112
113
114#ifdef BINARY_TREE
115static bdbuf_buffer *
116avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
117{
118    bdbuf_buffer *p = *root;
119    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
120    {
121        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
122            p = p->avl.right;
123        else
124            p = p->avl.left;
125    }
126    return p;
127}
128
129static bdbuf_buffer *
130avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
131{
132    bdbuf_buffer *p = *root;
133    bdbuf_buffer *s[32];
134    bdbuf_buffer **sp = s;
135    dev_t dev = dd->phys_dev->dev;
136    blkdev_bnum b = dd->start;
137    blkdev_bnum e = b + dd->size - 1;
138   
139    while (p != NULL)
140    {
141        if ((p->dev < dev) || ((p->dev == dev) && (p->block < b)))
142            p = p->avl.right;
143        else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e)))
144            p = p->avl.left;
145        else if (p->modified)
146            return p;
147        else
148        {
149            if (p->avl.right != NULL)
150                *sp++ = p->avl.right;
151            p = p->avl.left;
152        }
153        if ((p == NULL) && (sp > s))
154            p = *--sp;
155    }
156    return p;
157}
158
159static int
160avl_insert(bdbuf_buffer **root, bdbuf_buffer *node)
161{
162    bdbuf_buffer **r = root;
163    node->avl.left = node->avl.right = NULL;
164    while (TRUE)
165    {
166        bdbuf_buffer *rr = *r;
167        if (rr == NULL)
168        {
169            *r = node;
170            return 0;
171        }
172        else if ((rr->dev < node->dev) || ((rr->dev == node->dev) &&
173                                           (rr->block < node->block)))
174        {
175            r = &rr->avl.right;
176        }
177        else if ((rr->dev == node->dev) && (rr->block == node->block))
178        {
179            return -1;
180        }
181        else
182        {
183            r = &rr->avl.left;
184        }
185    }
186}
187
188static int
189avl_remove(bdbuf_buffer **root, bdbuf_buffer *node)
190{
191    bdbuf_buffer **p = root;
192    dev_t dev = node->dev;
193    blkdev_bnum block = node->block;
194   
195    while ((*p != NULL) && (*p != node))
196    {
197        if (((*p)->dev < dev) || (((*p)->dev == dev) && ((*p)->block < block)))
198            p = &(*p)->avl.right;
199        else
200            p = &(*p)->avl.left;
201    }
202    if (*p == NULL)
203        return -1;
204   
205    *p = node->avl.left;
206    while (*p != NULL)
207        p = &(*p)->avl.right;
208    *p = node->avl.right;
209    node->avl.left = node->avl.right = NULL;
210    return 0;
211}
212
213#else
214
215/* The default maximum height of 32 allows for AVL trees having
216   between 5,704,880 and 4,294,967,295 nodes, depending on order of
217   insertion.  You may change this compile-time constant as you
218   wish. */
219#ifndef AVL_MAX_HEIGHT
220#define AVL_MAX_HEIGHT  32
221#endif
222
223
224
225/*
226 * avl_cmp_node_node --
227 *     Compares two avl nodes. Function compares dev/block pairs of
228 *     the node1 and node2.
229 *
230 * PARAMETERS:
231 *     node1 - Pointer to the first node to compare
232 *     node2 - Pointer to the second node to compare
233 *
234 * RETURNS:
235 *     0 - dev/block of the nodes are equal
236 *     1 - dev/block of the second node are less
237 *    -1 - dev/block of the first node are less
238 */
239static inline int 
240avl_cmp_node_node(const bdbuf_buffer *const node1,
241                  const bdbuf_buffer *const node2)
242{
243    if (node1->dev < node2->dev)
244        return -1;
245    else if (node1->dev > node2->dev)
246        return +1;
247    else if (node1->block < node2->block)
248        return -1;
249    else if (node1->block > node2->block)
250        return +1;
251    else
252        return 0;
253}
254
255/*
256 * avl_cmp_node_pattern -
257 *     compares the dev/block of the node with specified two.
258 *
259 * PARAMETERS:
260 *     node1     - Pointer to the node to compare
261 *     dev/block - The pattern to compare with
262 *
263 * RETURNS:
264 *     0 - dev/block of the node and specified are equal
265 *     1 - dev/block specified are less
266 *    -1 - dev/block of the first node are less
267 *
268 */
269static inline int 
270avl_cmp_node_pattern(const bdbuf_buffer *const node1,
271                     dev_t dev,
272                     blkdev_bnum block)
273{
274    if (node1->dev < dev)
275        return -1;
276    else if (node1->dev > dev)
277        return +1;
278    else if (node1->block < block)
279        return -1;
280    else if (node1->block > block)
281        return +1;
282    else
283        return 0;
284}
285
286
287/*
288 * avl_search --
289 *     Searches for the node with specified dev/block.
290 *
291 * PARAMETERS:
292 *     root - pointer to the root node of the AVL-Tree.
293 *     dev, block - search key
294 *
295 * RETURNS:
296 *     NULL if node with specified dev/block not found
297 *     non-NULL - pointer to the node with specified dev/block
298 */
299static bdbuf_buffer *
300avl_search(bdbuf_buffer **root, dev_t dev, blkdev_bnum block)
301{
302
303    bdbuf_buffer *p = *root;
304    while ((p != NULL) && ((p->dev != dev) || (p->block != block)))
305    {
306        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
307            p = p->avl.link[1];
308        else
309            p = p->avl.link[0];
310    }
311    return p;
312}
313
314/* avl_search_for_sync --
315 *     Search in AVL tree for first modified buffer belongs to specified
316 *     disk device.
317 *
318 * PARAMETERS:
319 *     root - pointer to tree root
320 *     dd - disk device descriptor
321 *
322 * RETURNS:
323 *     Block buffer, or NULL if no modified blocks on specified device
324 *     exists.
325 */
326static bdbuf_buffer *
327avl_search_for_sync(bdbuf_buffer **root, disk_device *dd)
328{
329    bdbuf_buffer *p = *root;
330    bdbuf_buffer *s[AVL_MAX_HEIGHT];
331    bdbuf_buffer **sp = s;
332    dev_t dev = dd->phys_dev->dev;
333    blkdev_bnum b = dd->start;
334    blkdev_bnum e = b + dd->size - 1;
335   
336    while (p != NULL)
337    {
338        if ((p->dev < dev) || ((p->dev == dev) && (p->block < b)))
339            p = p->avl.link[1];
340        else if ((p->dev > dev) || ((p->dev == dev) && (p->block > e)))
341            p = p->avl.link[0];
342        else if (p->modified)
343            return p;
344        else
345        {
346            if (p->avl.link[1] != NULL)
347                *sp++ = p->avl.link[1];
348            p = p->avl.link[0];
349        }
350        if ((p == NULL) && (sp > s))
351            p = *--sp;
352    }
353    return p;
354}
355
356
357/*
358 * avl_insert --
359 *     Inserts the specified node to the AVl-Tree.
360 *
361 * PARAMETERS:
362 *     root_addr - Pointer to pointer to the root node
363 *     node - Pointer to the node to add.
364 *
365 * RETURNS:
366 *     0 - The node added successfully
367 *    -1 - An error occured
368 */
369static int
370avl_insert (bdbuf_buffer **root_addr, bdbuf_buffer *node)
371{
372    /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
373       insertion), but caches results of comparisons.  In empirical
374       tests this eliminates about 25% of the comparisons seen under
375       random insertions.  */
376
377  /* A1. */
378    int t_modified = 0;
379    bdbuf_buffer *t;
380    bdbuf_buffer *s, *p, *q, *r;
381
382    bdbuf_buffer *root_link = *root_addr;;
383
384    t = root_link;
385    s = p = t;
386
387    if (s == NULL)
388    {
389        q = t = node;
390        q->avl.link[0] = q->avl.link[1] = NULL;
391        q->avl.bal = 0;
392        *root_addr = t;
393        return 0;
394    }
395
396    for (;;)
397    {
398        /* A2. */
399        int diff = avl_cmp_node_node(node, p);
400
401      /* A3. */
402        if (diff < 0)
403        {
404            p->avl.cache = 0;
405            q = p->avl.link[0];
406            if (q == NULL)
407            {
408                p->avl.link[0] = q = node;
409                break;
410            }
411        }
412        /* A4. */
413        else 
414            if (diff > 0)
415            {
416                p->avl.cache = 1;
417                q = p->avl.link[1];
418                if (q == NULL)
419                {
420                    p->avl.link[1] = q = node;
421                    break;
422                }
423            }
424            else
425                /* A2. */
426            {
427                /*
428                 * The item found. Nothing changed. Have not to update
429                 * root_adr*/
430
431                return -1;
432            }
433
434        /* A3, A4. */
435        if (q->avl.bal != 0)
436        {
437            t = p, s = q;
438            t_modified = 1;
439        }
440        p = q;
441    }
442 
443    /* A5. */
444    q->avl.link[0] = q->avl.link[1] = NULL;
445    q->avl.bal = 0;
446
447    /* A6. */
448    r = p = s->avl.link[(int) s->avl.cache];
449    while (p != q)
450    {
451        p->avl.bal = p->avl.cache * 2 - 1;
452        p = p->avl.link[(int) p->avl.cache];
453    }
454
455    /* A7. */
456    if (s->avl.cache == 0)
457    {
458        /* a = -1. */
459        if (s->avl.bal == 0)
460        {
461            s->avl.bal = -1;
462            *root_addr = root_link;
463            return 0;
464        }
465        else if (s->avl.bal == +1)
466        {
467            s->avl.bal = 0;
468            *root_addr = root_link;
469            return 0;
470        }
471     
472        assert (s->avl.bal == -1);
473        if (r->avl.bal == -1)
474        {
475            /* A8. */
476            p = r;
477            s->avl.link[0] = r->avl.link[1];
478            r->avl.link[1] = s;
479            s->avl.bal = r->avl.bal = 0;
480        }
481        else
482        {
483            /* A9. */
484            assert(r->avl.bal == +1);
485            p = r->avl.link[1];
486            r->avl.link[1] = p->avl.link[0];
487            p->avl.link[0] = r;
488            s->avl.link[0] = p->avl.link[1];
489            p->avl.link[1] = s;
490            if (p->avl.bal == -1)
491                s->avl.bal = 1, r->avl.bal = 0;
492            else 
493            {
494                if (p->avl.bal == 0)
495                {
496                    s->avl.bal = r->avl.bal = 0;
497                }
498                else 
499                {
500                    assert (p->avl.bal == +1);
501                    s->avl.bal = 0, r->avl.bal = -1;
502                }
503            }
504            p->avl.bal = 0;
505        }
506    }
507    else
508    {
509        /* a == +1. */
510        if (s->avl.bal == 0)
511        {
512            s->avl.bal = 1;
513            *root_addr = root_link;
514            return 0;
515        } 
516        else if (s->avl.bal == -1)
517        {
518            s->avl.bal = 0;
519            *root_addr = root_link;
520            return 0;
521        }
522
523        assert(s->avl.bal == +1);
524        if (r->avl.bal == +1)
525        {
526            /* A8. */
527            p = r;
528            s->avl.link[1] = r->avl.link[0];
529            r->avl.link[0] = s;
530            s->avl.bal = r->avl.bal = 0;
531        }
532        else
533        {
534            /* A9. */
535            assert(r->avl.bal == -1);
536            p = r->avl.link[0];
537            r->avl.link[0] = p->avl.link[1];
538            p->avl.link[1] = r;
539            s->avl.link[1] = p->avl.link[0];
540            p->avl.link[0] = s;
541            if (p->avl.bal == +1)
542            {
543                s->avl.bal = -1, r->avl.bal = 0;
544            }
545            else 
546            {
547                if (p->avl.bal == 0)
548                {
549                    s->avl.bal = r->avl.bal = 0;
550                }
551                else 
552                {
553                    assert(p->avl.bal == -1);
554                    s->avl.bal = 0, r->avl.bal = 1;
555                }
556            }
557            p->avl.bal = 0;
558        }
559    }
560               
561    /* A10. */
562    if (t_modified)
563    {
564        if (s == t->avl.link[1])
565            t->avl.link[1] = p;
566        else
567            t->avl.link[0] = p;
568    }
569    else
570    {
571        root_link = p;
572    }
573
574    *root_addr = root_link;
575    return 0;
576}
577
578
579/* avl_remove --
580 *     removes the node from the tree.
581 *
582 * PARAMETERS:
583 *     root_addr - Pointer to pointer to the root node
584 *     node      - Pointer to the node to remove
585 *
586 * RETURNS:
587 *     0 - Item removed
588 *    -1 - No such item found
589 */
590static int
591avl_remove(bdbuf_buffer **root_addr, const bdbuf_buffer *node)
592{
593    /* Uses my Algorithm D, which can be found at
594       http://www.msu.edu/user/pfaffben/avl.  Algorithm D is based on
595       Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced
596       tree search and insertion), as well as the notes on pages 465-466
597       of Vol. 3. */
598
599  /* D1. */
600    bdbuf_buffer *pa[AVL_MAX_HEIGHT];           /* Stack P: Nodes. */
601    char a[AVL_MAX_HEIGHT];             /* Stack P: Bits. */
602    int k = 1;                          /* Stack P: Pointer. */
603 
604    bdbuf_buffer **q;
605    bdbuf_buffer *p;
606
607
608    /*
609     * To avoid using unnessary instance of the 'bdbuf_buffer' (as pa[0])
610     * we will catch all access to pa[0] and use &root_avl instead
611     */
612    struct bdbuf_avl_node root_avl;
613
614    root_avl.link[0] = *root_addr;
615    root_avl.link[1] = NULL;
616    root_avl.bal = 0;
617    root_avl.cache = 0;
618
619    a[0] = 0;
620
621    p = root_avl.link[0];
622
623
624    k = 1;
625
626    for (;;)
627    {
628        /* D2. */
629        int diff;
630
631        if (p == NULL)
632            return -1;
633
634        diff = avl_cmp_node_node(node, p);
635
636        if (diff == 0)
637            break;
638
639      /* D3, D4. */
640        pa[k] = p;
641        if (diff < 0)
642        {
643            p = p->avl.link[0];
644            a[k] = 0;
645        }
646        else if (diff > 0)
647        {
648            p = p->avl.link[1];
649            a[k] = 1;
650        }
651        k++;
652    }
653
654    /* D5. */
655    if (k == 1)
656    {
657        /* Andron */
658        q = &root_avl.link[(int) a[k - 1]];
659    }
660    else
661    {
662        q = &pa[k - 1]->avl.link[(int) a[k - 1]];
663    }
664    if (p->avl.link[1] == NULL)
665    {
666        *q = p->avl.link[0];
667        if (*q)
668            (*q)->avl.bal = 0;
669    }
670    else
671    {
672        /* D6. */
673        bdbuf_buffer *r = p->avl.link[1];
674        if (r->avl.link[0] == NULL)
675        {
676            r->avl.link[0] = p->avl.link[0];
677            *q = r;
678            r->avl.bal = p->avl.bal;
679            a[k] = 1;
680            pa[k++] = r;
681        }
682        else
683        {
684            /* D7. */
685            bdbuf_buffer *s = r->avl.link[0];
686            int l = k++;
687
688            a[k] = 0;
689            pa[k++] = r;
690           
691            /* D8. */
692            while (s->avl.link[0] != NULL)
693            {
694                r = s;
695                s = r->avl.link[0];
696                a[k] = 0;
697                pa[k++] = r;
698            }
699
700            /* D9. */
701            a[l] = 1;
702            pa[l] = s;
703            s->avl.link[0] = p->avl.link[0];
704            r->avl.link[0] = s->avl.link[1];
705            s->avl.link[1] = p->avl.link[1];
706            s->avl.bal = p->avl.bal;
707            *q = s;
708        }
709    }
710
711    assert(k > 0);
712    /* D10. */
713    while (--k)
714    {
715        bdbuf_buffer *s = pa[k], *r;
716
717        if (a[k] == 0)
718        {
719            /* D10. */
720            if (s->avl.bal == -1)
721            {
722                s->avl.bal = 0;
723                continue;
724            }
725            else if (s->avl.bal == 0)
726            { 
727                s->avl.bal = 1;
728                break;
729            }
730
731            assert(s->avl.bal == +1);
732            r = s->avl.link[1];
733
734            assert(r != NULL);
735            if (r->avl.bal == 0)
736            {
737                /* D11. */
738                s->avl.link[1] = r->avl.link[0];
739                r->avl.link[0] = s;
740                r->avl.bal = -1;
741                if (k == 1)
742                {
743                    /* Andron */
744                    root_avl.link[(int) a[k - 1]] = r;
745                }
746                else
747                {
748                    pa[k - 1]->avl.link[(int) a[k - 1]] = r;
749                }
750                break;
751            }
752            else 
753                if (r->avl.bal == +1)
754                {
755                    /* D12. */
756                    s->avl.link[1] = r->avl.link[0];
757                    r->avl.link[0] = s;
758                    s->avl.bal = r->avl.bal = 0;
759                    if (k == 1)
760                    {
761                        /* Andron */
762                        root_avl.link[(int) a[k - 1]] = r;
763                    }
764                    else
765                    {
766                        pa[k - 1]->avl.link[(int) a[k - 1]] = r;
767                    }
768                }
769                else 
770                {
771                    /* D13. */
772                    assert(r->avl.bal == -1);
773                    p = r->avl.link[0];
774                    r->avl.link[0] = p->avl.link[1];
775                    p->avl.link[1] = r;
776                    s->avl.link[1] = p->avl.link[0];
777                    p->avl.link[0] = s;
778                    if (p->avl.bal == +1)
779                        s->avl.bal = -1, r->avl.bal = 0;
780                    else if (p->avl.bal == 0)
781                    {
782                        s->avl.bal = r->avl.bal = 0;
783                    }
784                    else
785                    {
786                        assert(p->avl.bal == -1);
787                        s->avl.bal = 0, r->avl.bal = +1;
788                    }
789                    p->avl.bal = 0;
790                    if (k == 1)
791                    {
792                        /* Andron */
793                        root_avl.link[(int) a[k - 1]] = p;
794                    }
795                    else
796                    {
797                        pa[k - 1]->avl.link[(int) a[k - 1]] = p;
798                    }
799                }
800        }
801        else
802        {
803            assert(a[k] == 1);
804
805            /* D10. */
806            if (s->avl.bal == +1)
807            {
808                s->avl.bal = 0;
809                continue;
810            }
811            else 
812                if (s->avl.bal == 0)
813                {
814                    s->avl.bal = -1;
815                    break;
816                }
817
818            assert(s->avl.bal == -1);
819            r = s->avl.link[0];
820
821            if (r == NULL || r->avl.bal == 0)
822            {
823                /* D11. */
824                s->avl.link[0] = r->avl.link[1];
825                r->avl.link[1] = s;
826                r->avl.bal = 1;
827                if (k == 1)
828                {
829                    /* Andron */
830                    root_avl.link[(int) a[k - 1]] = r;
831                }
832                else
833                {
834                    pa[k - 1]->avl.link[(int) a[k - 1]] = r;
835                }
836
837                break;
838            }
839            else 
840                if (r->avl.bal == -1)
841                {
842                    /* D12. */
843                    s->avl.link[0] = r->avl.link[1];
844                    r->avl.link[1] = s;
845                    s->avl.bal = r->avl.bal = 0;
846                    if (k == 1)
847                    {
848                        root_avl.link[(int) a[k - 1]] = r;
849                    }
850                    else
851                    {
852                        pa[k - 1]->avl.link[(int) a[k - 1]] = r;
853                    }
854
855                }
856                else 
857                    if (r->avl.bal == +1)
858                    {
859                        /* D13. */
860                        p = r->avl.link[1];
861                        r->avl.link[1] = p->avl.link[0];
862                        p->avl.link[0] = r;
863                        s->avl.link[0] = p->avl.link[1];
864                        p->avl.link[1] = s;
865                        if (p->avl.bal == -1)
866                            s->avl.bal = 1, r->avl.bal = 0;
867                        else 
868                            if (p->avl.bal == 0)
869                                s->avl.bal = r->avl.bal = 0;
870                            else
871                            {
872                                assert(p->avl.bal == 1);
873                                s->avl.bal = 0, r->avl.bal = -1;
874                            }
875                        p->avl.bal = 0;
876                        if (k == 1)
877                        {
878                            /* Andron */
879                            root_avl.link[(int) a[k - 1]] = p;
880                        }
881                        else
882                        {
883                            pa[k - 1]->avl.link[(int) a[k - 1]] = p;
884                        }
885                    }
886        }
887    }
888
889    *root_addr = root_avl.link[0];
890    return 0;
891}
892
893#endif
894
895/* bdbuf_initialize_pool --
896 *      Initialize single buffer pool.
897 *
898 * PARAMETERS:
899 *     config - buffer pool configuration
900 *     pool   - pool number
901 *
902 * RETURNS:
903 *     RTEMS_SUCCESSFUL, if buffer pool initialized successfully, or error
904 *     code if error occured.
905 */
906static rtems_status_code
907bdbuf_initialize_pool(rtems_bdbuf_config *config, int pool)
908{
909    bdbuf_pool *p = bd_ctx.pool + pool;
910    unsigned char *bufs;
911    bdbuf_buffer *b;
912    rtems_status_code rc;
913    int i;
914   
915    p->blksize = config->size;
916    p->nblks = config->num;
917    p->tree = NULL;
918   
919    Chain_Initialize_empty(&p->free);
920    Chain_Initialize_empty(&p->lru);
921   
922    /* Allocate memory for buffer descriptors */
923    p->bdbufs = calloc(config->num, sizeof(bdbuf_buffer));
924    if (p->bdbufs == NULL)
925    {
926        return RTEMS_NO_MEMORY;
927    }
928   
929    /* Allocate memory for buffers if required */
930    if (config->mem_area == NULL)
931    {
932        bufs = p->mallocd_bufs = malloc(config->num * config->size);
933        if (bufs == NULL)
934        {
935            free(p->bdbufs);
936            return RTEMS_NO_MEMORY;
937        }
938    }
939    else
940    {
941        bufs = config->mem_area;
942        p->mallocd_bufs = NULL;
943    }
944   
945    for (i = 0, b = p->bdbufs; i < p->nblks; i++, b++, bufs += p->blksize)
946    {
947        b->dev = -1; b->block = 0;
948        b->buffer = bufs;
949        b->actual = b->modified = b->in_progress = FALSE;
950        b->use_count = 0;
951        b->pool = pool;
952        _Chain_Append(&p->free, &b->link);
953    }
954   
955    rc = rtems_semaphore_create(
956        rtems_build_name('B', 'U', 'F', 'G'),
957        p->nblks,
958        RTEMS_FIFO | RTEMS_COUNTING_SEMAPHORE | RTEMS_NO_INHERIT_PRIORITY |
959        RTEMS_NO_PRIORITY_CEILING | RTEMS_LOCAL,
960        0,
961        &p->bufget_sema);
962   
963    if (rc != RTEMS_SUCCESSFUL)
964    {
965        free(p->bdbufs);
966        free(p->mallocd_bufs);
967        return rc;
968    }
969   
970    return RTEMS_SUCCESSFUL;
971}
972
973/* bdbuf_release_pool --
974 *     Free resources allocated for buffer pool with specified number.
975 *
976 * PARAMETERS:
977 *     pool - buffer pool number
978 *
979 * RETURNS:
980 *     RTEMS_SUCCESSFUL
981 */
982static rtems_status_code
983bdbuf_release_pool(rtems_bdpool_id pool)
984{
985    bdbuf_pool *p = bd_ctx.pool + pool;
986    rtems_semaphore_delete(p->bufget_sema);
987    free(p->bdbufs);
988    free(p->mallocd_bufs);
989    return RTEMS_SUCCESSFUL;
990}
991
992/* rtems_bdbuf_init --
993 *     Prepare buffering layer to work - initialize buffer descritors
994 *     and (if it is neccessary)buffers. Buffers will be allocated accoriding
995 *     to the configuration table, each entry describes kind of block and
996 *     amount requested. After initialization all blocks is placed into
997 *     free elements lists.
998 *
999 * PARAMETERS:
1000 *     conf_table - pointer to the buffers configuration table
1001 *     size       - number of entries in configuration table
1002 *
1003 * RETURNS:
1004 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1005 *     or error code if error is occured)
1006 */
1007rtems_status_code
1008rtems_bdbuf_init(rtems_bdbuf_config *conf_table, int size)
1009{
1010    rtems_bdpool_id i;
1011    rtems_status_code rc;
1012
1013    if (size <= 0)
1014        return RTEMS_INVALID_SIZE;
1015   
1016    bd_ctx.npools = size;
1017
1018    /*
1019     * Allocate memory for buffer pool descriptors
1020     */
1021    bd_ctx.pool = calloc(size, sizeof(bdbuf_pool));
1022    if (bd_ctx.pool == NULL)
1023    {
1024        return RTEMS_NO_MEMORY;
1025    }
1026
1027    Chain_Initialize_empty(&bd_ctx.mod);
1028   
1029    /* Initialize buffer pools and roll out if something failed */
1030    for (i = 0; i < size; i++)
1031    {
1032        rc = bdbuf_initialize_pool(conf_table + i, i);
1033        if (rc != RTEMS_SUCCESSFUL)
1034        {
1035             rtems_bdpool_id j;
1036             for (j = 0; j < i - 1; j++)
1037             {
1038                 bdbuf_release_pool(j);
1039             }
1040             return rc;
1041        }
1042    }
1043
1044    /* Create buffer flush semaphore */
1045    rc = rtems_semaphore_create(
1046        rtems_build_name('B', 'F', 'L', 'U'), 0,
1047        RTEMS_FIFO | RTEMS_COUNTING_SEMAPHORE | RTEMS_NO_INHERIT_PRIORITY |
1048        RTEMS_NO_PRIORITY_CEILING | RTEMS_LOCAL, 0,
1049        &bd_ctx.flush_sema);
1050    if (rc != RTEMS_SUCCESSFUL)
1051    {
1052        for (i = 0; i < size; i++)
1053            bdbuf_release_pool(i);
1054        free(bd_ctx.pool);
1055        return rc;
1056    }
1057   
1058    /* Create and start swapout task */
1059    rc = rtems_task_create(
1060        rtems_build_name('B', 'S', 'W', 'P'),
1061        SWAPOUT_PRIORITY,
1062        SWAPOUT_STACK_SIZE, 
1063        RTEMS_DEFAULT_MODES | RTEMS_NO_PREEMPT,
1064        RTEMS_DEFAULT_ATTRIBUTES,
1065        &bd_ctx.swapout_task);
1066    if (rc != RTEMS_SUCCESSFUL)
1067    {
1068        rtems_semaphore_delete(bd_ctx.flush_sema);
1069        for (i = 0; i < size; i++)
1070            bdbuf_release_pool(i);
1071        free(bd_ctx.pool);
1072        return rc;
1073    }
1074
1075    rc = rtems_task_start(bd_ctx.swapout_task, bdbuf_swapout_task, 0);
1076    if (rc != RTEMS_SUCCESSFUL)
1077    {
1078        rtems_task_delete(bd_ctx.swapout_task);
1079        rtems_semaphore_delete(bd_ctx.flush_sema);
1080        for (i = 0; i < size; i++)
1081            bdbuf_release_pool(i);
1082        free(bd_ctx.pool);
1083        return rc;
1084    }
1085
1086    return RTEMS_SUCCESSFUL;
1087}
1088
1089/* find_or_assign_buffer --
1090 *     Looks for buffer already assigned for this dev/block. If one is found
1091 *     obtain block buffer. If specified block already cached (i.e. there's
1092 *     block in the _modified_, or _recently_used_), return address
1093 *     of appropriate buffer descriptor and increment reference counter to 1.
1094 *     If block is not cached, allocate new buffer and return it. Data
1095 *     shouldn't be read to the buffer from media; buffer contains arbitrary
1096 *     data. This primitive may be blocked if there are no free buffer
1097 *     descriptors available and there are no unused non-modified (or
1098 *     synchronized with media) buffers available.
1099 *
1100 * PARAMETERS:
1101 *     device - device number (constructed of major and minor device number
1102 *     block  - linear media block number
1103 *     ret_buf - address of the variable to store address of found descriptor
1104 *
1105 * RETURNS:
1106 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1107 *     or error code if error is occured)
1108 *
1109 * SIDE EFFEECTS:
1110 *     bufget_sema may be obtained by this primitive
1111 *
1112 * NOTE:
1113 *     It is assumed that primitive invoked when thread preemption is disabled.
1114 */
1115static rtems_status_code
1116find_or_assign_buffer(disk_device *dd,
1117                      blkdev_bnum block, 
1118                      bdbuf_buffer **ret_buf)
1119{
1120    bdbuf_buffer *bd_buf;
1121    bdbuf_pool   *bd_pool;
1122    rtems_status_code rc;
1123    dev_t         device;
1124    ISR_Level     level;
1125
1126    int blksize;
1127
1128    device = dd->dev;
1129    bd_pool = bd_ctx.pool + dd->pool;
1130    blksize = dd->block_size;
1131
1132again:
1133    /* Looking for buffer descriptor used for this dev/block. */
1134    bd_buf = avl_search(&bd_pool->tree, device, block);
1135
1136    if (bd_buf == NULL)
1137    {
1138        /* Try to obtain semaphore without waiting first. It is the most
1139           frequent case when reasonable number of buffers configured. If
1140           it is failed, obtain semaphore blocking on it. In this case
1141           it should be checked that appropriate buffer hasn't been loaded
1142           by another thread, because this thread is preempted */
1143        rc = rtems_semaphore_obtain(bd_pool->bufget_sema, RTEMS_NO_WAIT, 0);
1144        if (rc == RTEMS_UNSATISFIED)
1145        {
1146            rc = rtems_semaphore_obtain(bd_pool->bufget_sema,
1147                                        RTEMS_WAIT, RTEMS_NO_TIMEOUT);
1148            bd_buf = avl_search(&bd_pool->tree, device, block);
1149            if (bd_buf != NULL)
1150                rtems_semaphore_release(bd_pool->bufget_sema);
1151        }
1152    }
1153   
1154    if (bd_buf == NULL)
1155    {
1156        /* Assign new buffer descriptor */
1157        if (_Chain_Is_empty(&bd_pool->free))
1158        {
1159            bd_buf = (bdbuf_buffer *)Chain_Get(&bd_pool->lru);
1160            if (bd_buf != NULL)
1161            {
1162                int avl_result; 
1163                avl_result = avl_remove(&bd_pool->tree, bd_buf);
1164                if (avl_result != 0)
1165                {
1166                    rtems_fatal_error_occurred(BLKDEV_FATAL_BDBUF_CONSISTENCY);
1167                    return RTEMS_INTERNAL_ERROR;
1168                }
1169            }
1170        }
1171        else
1172        {
1173            bd_buf = (bdbuf_buffer *)Chain_Get(&(bd_pool->free));
1174        }
1175
1176        if (bd_buf == NULL)
1177        {
1178            goto again;
1179        }
1180        else
1181        {
1182            bd_buf->dev = device;
1183            bd_buf->block = block;
1184#ifdef BINARY_TREE
1185            bd_buf->avl.left = NULL;
1186            bd_buf->avl.right = NULL;
1187#else
1188            bd_buf->avl.link[0] = NULL;
1189            bd_buf->avl.link[1] = NULL;
1190#endif
1191            bd_buf->use_count = 1;
1192            bd_buf->modified = bd_buf->actual = bd_buf->in_progress = FALSE;
1193            bd_buf->status = RTEMS_SUCCESSFUL;
1194
1195            if (avl_insert(&bd_pool->tree, bd_buf) != 0)
1196            {
1197                rtems_fatal_error_occurred(BLKDEV_FATAL_BDBUF_CONSISTENCY);
1198                return RTEMS_INTERNAL_ERROR;
1199            }
1200
1201            *ret_buf = bd_buf;
1202
1203            return RTEMS_SUCCESSFUL;
1204        }
1205    }
1206    else
1207    {
1208        /* Buffer descriptor already assigned for this dev/block */
1209        if (bd_buf->use_count == 0)
1210        {
1211            /* If we are removing from lru list, obtain the bufget_sema
1212             * first. If we are removing from mod list, obtain flush sema.
1213             * It should be obtained without blocking because we know
1214             * that our buffer descriptor is in the list. */
1215            if (bd_buf->modified)
1216            {
1217                rc = rtems_semaphore_obtain(bd_ctx.flush_sema, 
1218                                            RTEMS_NO_WAIT, 0);
1219            }
1220            else
1221            {
1222                rc = rtems_semaphore_obtain(bd_pool->bufget_sema, 
1223                                            RTEMS_NO_WAIT, 0);
1224            }
1225            /* It is possible that we couldn't obtain flush or bufget sema
1226             * although buffer in the appropriate chain is available:
1227             * semaphore may be released to swapout task, but this task
1228             * actually did not start to process it. */
1229            if (rc == RTEMS_UNSATISFIED)
1230                rc = RTEMS_SUCCESSFUL;
1231            if (rc != RTEMS_SUCCESSFUL)
1232            {
1233                rtems_fatal_error_occurred(BLKDEV_FATAL_BDBUF_CONSISTENCY);
1234                return RTEMS_INTERNAL_ERROR;
1235            }
1236
1237            /* Buffer descriptor is linked to the lru or mod chain. Remove
1238               it from there. */
1239            Chain_Extract(&bd_buf->link);
1240        }
1241        bd_buf->use_count++;
1242        while (bd_buf->in_progress != 0)
1243        {
1244            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
1245                              WATCHDOG_NO_TIMEOUT, level);
1246        }
1247       
1248        *ret_buf = bd_buf;
1249        return RTEMS_SUCCESSFUL;
1250    }
1251}
1252
1253/* rtems_bdbuf_get --
1254 *     Obtain block buffer. If specified block already cached (i.e. there's
1255 *     block in the _modified_, or _recently_used_), return address
1256 *     of appropriate buffer descriptor and increment reference counter to 1.
1257 *     If block is not cached, allocate new buffer and return it. Data
1258 *     shouldn't be read to the buffer from media; buffer may contains
1259 *     arbitrary data. This primitive may be blocked if there are no free
1260 *     buffer descriptors available and there are no unused non-modified
1261 *     (or synchronized with media) buffers available.
1262 *
1263 * PARAMETERS:
1264 *     device - device number (constructed of major and minor device number)
1265 *     block  - linear media block number
1266 *     bd     - address of variable to store pointer to the buffer descriptor
1267 *
1268 * RETURNS:
1269 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1270 *     or error code if error is occured)
1271 *
1272 * SIDE EFFECTS:
1273 *     bufget_sema semaphore obtained by this primitive.
1274 */
1275rtems_status_code
1276rtems_bdbuf_get(dev_t device, blkdev_bnum block, bdbuf_buffer **bd)
1277{
1278    rtems_status_code rc;
1279    disk_device *dd;
1280    disk_device *pdd;
1281    preemption_key key;
1282
1283    /*
1284     * Convert logical dev/block to physical one
1285     */
1286    dd = rtems_disk_lookup(device);
1287    if (dd == NULL)
1288        return RTEMS_INVALID_ID;
1289   
1290    if (block >= dd->size)
1291    {
1292        rtems_disk_release(dd);
1293        return RTEMS_INVALID_NUMBER;
1294    }
1295   
1296    pdd = dd->phys_dev;
1297    block += dd->start;
1298    rtems_disk_release(dd);
1299
1300    DISABLE_PREEMPTION(key);
1301    rc = find_or_assign_buffer(pdd, block, bd);
1302    ENABLE_PREEMPTION(key);
1303
1304    if (rc != RTEMS_SUCCESSFUL)
1305        return rc;
1306
1307    return RTEMS_SUCCESSFUL;
1308}
1309
1310/* bdbuf_initialize_transfer_sema --
1311 *     Initialize transfer_sema mutex semaphore associated with buffer
1312 *     descriptor.
1313 */
1314static inline void
1315bdbuf_initialize_transfer_sema(bdbuf_buffer *bd_buf)
1316{
1317    CORE_mutex_Attributes mutex_attr;
1318    mutex_attr.lock_nesting_behavior = CORE_MUTEX_NESTING_BLOCKS;
1319    mutex_attr.only_owner_release = FALSE;
1320    mutex_attr.discipline = CORE_MUTEX_DISCIPLINES_FIFO;
1321    mutex_attr.priority_ceiling = 0;
1322
1323    _CORE_mutex_Initialize(&bd_buf->transfer_sema, OBJECTS_NO_CLASS,
1324                           &mutex_attr, CORE_MUTEX_LOCKED, NULL);
1325}
1326
1327/* bdbuf_write_transfer_done --
1328 *     Callout function. Invoked by block device driver when data transfer
1329 *     to device (write) is completed. This function may be invoked from
1330 *     interrupt handler.
1331 *
1332 * PARAMETERS:
1333 *     arg    - arbitrary argument specified in block device request
1334 *              structure (in this case - pointer to the appropriate
1335 *              bdbuf_buffer buffer descriptor structure).
1336 *     status - I/O completion status
1337 *     error  - errno error code if status != RTEMS_SUCCESSFUL
1338 *
1339 * RETURNS:
1340 *     none
1341 */
1342static void
1343bdbuf_write_transfer_done(void *arg, rtems_status_code status, int error)
1344{
1345    bdbuf_buffer *bd_buf = arg;
1346    bd_buf->status = status;
1347    bd_buf->error = error;
1348    bd_buf->in_progress = bd_buf->modified = FALSE;
1349    _CORE_mutex_Surrender(&bd_buf->transfer_sema, 0, NULL);
1350    _CORE_mutex_Flush(&bd_buf->transfer_sema, NULL, 
1351                      CORE_MUTEX_STATUS_SUCCESSFUL);
1352}
1353
1354/* bdbuf_read_transfer_done --
1355 *     Callout function. Invoked by block device driver when data transfer
1356 *     from device (read) is completed. This function may be invoked from
1357 *     interrupt handler.
1358 *
1359 * PARAMETERS:
1360 *     arg    - arbitrary argument specified in block device request
1361 *              structure (in this case - pointer to the appropriate
1362 *              bdbuf_buffer buffer descriptor structure).
1363 *     status - I/O completion status
1364 *     error  - errno error code if status != RTEMS_SUCCESSFUL
1365 *
1366 * RETURNS:
1367 *     none
1368 */
1369static void
1370bdbuf_read_transfer_done(void *arg, rtems_status_code status, int error)
1371{
1372    bdbuf_buffer *bd_buf = arg;
1373    bd_buf->status = status;
1374    bd_buf->error = error;
1375    _CORE_mutex_Surrender(&bd_buf->transfer_sema, 0, NULL);
1376    _CORE_mutex_Flush(&bd_buf->transfer_sema, NULL, 
1377                      CORE_MUTEX_STATUS_SUCCESSFUL);
1378}
1379
1380/* rtems_bdbuf_read --
1381 *     (Similar to the rtems_bdbuf_get, except reading data from media)
1382 *     Obtain block buffer. If specified block already cached, return address
1383 *     of appropriate buffer and increment reference counter to 1. If block is
1384 *     not cached, allocate new buffer and read data to it from the media.
1385 *     This primitive may be blocked on waiting until data to be read from
1386 *     media, if there are no free buffer descriptors available and there are
1387 *     no unused non-modified (or synchronized with media) buffers available.
1388 *
1389 * PARAMETERS:
1390 *     device - device number (consists of major and minor device number)
1391 *     block  - linear media block number
1392 *     bd     - address of variable to store pointer to the buffer descriptor
1393 *
1394 * RETURNS:
1395 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1396 *     or error code if error is occured)
1397 *
1398 * SIDE EFFECTS:
1399 *     bufget_sema and transfer_sema semaphores obtained by this primitive.
1400 */
1401rtems_status_code
1402rtems_bdbuf_read(dev_t device, 
1403                 blkdev_bnum block,
1404                 bdbuf_buffer **bd)
1405{
1406    preemption_key key;
1407    ISR_Level level;
1408   
1409    bdbuf_buffer *bd_buf;
1410    rtems_status_code rc;
1411    int result;
1412    disk_device *dd;
1413    disk_device *pdd;
1414    blkdev_request1 req;
1415
1416    dd = rtems_disk_lookup(device);
1417    if (dd == NULL)
1418        return RTEMS_INVALID_ID;
1419     
1420    if (block >= dd->size)
1421    {
1422        rtems_disk_release(dd);
1423        return RTEMS_INVALID_NUMBER;
1424    }
1425   
1426    pdd = dd->phys_dev;
1427    block += dd->start;
1428
1429    DISABLE_PREEMPTION(key);
1430    rc = find_or_assign_buffer(pdd, block, &bd_buf);
1431
1432    if (rc != RTEMS_SUCCESSFUL)
1433    {
1434        ENABLE_PREEMPTION(key);
1435        rtems_disk_release(dd);
1436        return rc;
1437    }
1438
1439    if (!bd_buf->actual)
1440    {
1441        bd_buf->in_progress = 1;
1442
1443        req.req.req = BLKDEV_REQ_READ;
1444        req.req.req_done = bdbuf_read_transfer_done;
1445        req.req.done_arg = bd_buf;
1446        req.req.start = block;
1447        req.req.count = 1;
1448        req.req.bufnum = 1;
1449        req.req.bufs[0].length = dd->block_size;
1450        req.req.bufs[0].buffer = bd_buf->buffer;
1451       
1452        bdbuf_initialize_transfer_sema(bd_buf);
1453        result = dd->ioctl(device, BLKIO_REQUEST, &req);
1454        if (result == -1)
1455        {
1456            bd_buf->status = RTEMS_IO_ERROR;
1457            bd_buf->error = errno;
1458            bd_buf->actual = FALSE;
1459        }
1460        else
1461        {
1462            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
1463                              WATCHDOG_NO_TIMEOUT, level);
1464            bd_buf->actual = TRUE;
1465        }
1466        bd_buf->in_progress = FALSE;
1467    }
1468    rtems_disk_release(dd);
1469   
1470    ENABLE_PREEMPTION(key);
1471
1472    *bd = bd_buf;
1473           
1474    return RTEMS_SUCCESSFUL;
1475}
1476
1477
1478/* bdbuf_release --
1479 *     Release buffer. Decrease buffer usage counter. If it is zero, further
1480 *     processing depends on modified attribute. If buffer was modified, it
1481 *     is inserted into mod chain and swapout task waken up. If buffer was
1482 *     not modified, it is returned to the end of lru chain making it available
1483 *     for further use.
1484 *
1485 * PARAMETERS:
1486 *     bd_buf - pointer to the released buffer descriptor.
1487 *
1488 * RETURNS:
1489 *     RTEMS_SUCCESSFUL if buffer released successfully, or error code if
1490 *     error occured.
1491 *
1492 * NOTE:
1493 *     This is internal function. It is assumed that task made non-preemptive
1494 *     before its invocation.
1495 */
1496static rtems_status_code
1497bdbuf_release(bdbuf_buffer *bd_buf)
1498{
1499    bdbuf_pool *bd_pool;
1500    rtems_status_code rc = RTEMS_SUCCESSFUL;
1501
1502    if (bd_buf->use_count <= 0)
1503        return RTEMS_INTERNAL_ERROR;
1504   
1505    bd_pool = bd_ctx.pool + bd_buf->pool;
1506
1507    bd_buf->use_count--;
1508
1509    if (bd_buf->use_count == 0)
1510    {
1511        if (bd_buf->modified)
1512        {
1513           
1514            /* Buffer was modified. Insert buffer to the modified buffers
1515             * list and initiate flushing. */
1516            Chain_Append(&bd_ctx.mod, &bd_buf->link);
1517
1518            /* Release the flush_sema */
1519            rc = rtems_semaphore_release(bd_ctx.flush_sema);
1520        }
1521        else
1522        {
1523            /* Buffer was not modified. Add this descriptor to the
1524             * end of lru chain and make it available for reuse. */
1525            Chain_Append(&bd_pool->lru, &bd_buf->link);
1526            rc = rtems_semaphore_release(bd_pool->bufget_sema);
1527        }
1528    }
1529    return rc;
1530}
1531
1532
1533/* rtems_bdbuf_release --
1534 *     Release buffer allocated before. This primitive decrease the
1535 *     usage counter. If it is zero, further destiny of buffer depends on
1536 *     'modified' status. If buffer was modified, it is placed to the end of
1537 *     mod list and flush task waken up. If buffer was not modified,
1538 *     it is placed to the end of lru list, and bufget_sema released, allowing
1539 *     to reuse this buffer.
1540 *
1541 * PARAMETERS:
1542 *     bd_buf - pointer to the bdbuf_buffer structure previously obtained using
1543 *              get/read primitive.
1544 *
1545 * RETURNS:
1546 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1547 *     or error code if error is occured)
1548 *
1549 * SIDE EFFECTS:
1550 *     flush_sema and bufget_sema semaphores may be released by this primitive.
1551 */
1552rtems_status_code
1553rtems_bdbuf_release(bdbuf_buffer *bd_buf)
1554{
1555    preemption_key key;
1556    rtems_status_code rc = RTEMS_SUCCESSFUL;
1557
1558    if (bd_buf == NULL)
1559        return RTEMS_INVALID_ADDRESS;
1560   
1561    DISABLE_PREEMPTION(key);
1562   
1563    rc = bdbuf_release(bd_buf);
1564   
1565    ENABLE_PREEMPTION(key);
1566   
1567    return rc;
1568}
1569
1570/* rtems_bdbuf_release_modified --
1571 *     Release buffer allocated before, assuming that it is _modified_ by
1572 *     it's owner. This primitive decrease usage counter for buffer, mark
1573 *     buffer descriptor as modified. If usage counter is 0, insert it at
1574 *     end of mod chain and release flush_sema semaphore to activate the
1575 *     flush task.
1576 *
1577 * PARAMETERS:
1578 *     bd_buf - pointer to the bdbuf_buffer structure previously obtained using
1579 *              get/read primitive.
1580 *
1581 * RETURNS:
1582 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1583 *     or error code if error is occured)
1584 *
1585 * SIDE EFFECTS:
1586 *     flush_sema semaphore may be released by this primitive.
1587 */
1588rtems_status_code
1589rtems_bdbuf_release_modified(bdbuf_buffer *bd_buf)
1590{
1591    preemption_key key;
1592    rtems_status_code rc = RTEMS_SUCCESSFUL;
1593
1594    if (bd_buf == NULL)
1595        return RTEMS_INVALID_ADDRESS;
1596   
1597    DISABLE_PREEMPTION(key);
1598
1599    if (!bd_buf->modified)
1600    {
1601        bdbuf_initialize_transfer_sema(bd_buf);
1602    }
1603    bd_buf->modified = TRUE;
1604    bd_buf->actual = TRUE;
1605    rc = bdbuf_release(bd_buf);   
1606   
1607    ENABLE_PREEMPTION(key);
1608   
1609    return rc;
1610}
1611
1612/* rtems_bdbuf_sync --
1613 *     Wait until specified buffer synchronized with disk. Invoked on exchanges
1614 *     critical for data consistency on the media. This primitive mark owned
1615 *     block as modified, decrease usage counter. If usage counter is 0,
1616 *     block inserted to the mod chain and flush_sema semaphore released.
1617 *     Finally, primitives blocked on transfer_sema semaphore.
1618 *
1619 * PARAMETERS:
1620 *     bd_buf - pointer to the bdbuf_buffer structure previously obtained using
1621 *              get/read primitive.
1622 *
1623 * RETURNS:
1624 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1625 *     or error code if error is occured)
1626 *
1627 * SIDE EFFECTS:
1628 *     Primitive may be blocked on transfer_sema semaphore.
1629 */
1630rtems_status_code
1631rtems_bdbuf_sync(bdbuf_buffer *bd_buf)
1632{
1633    preemption_key key;
1634    ISR_Level level;
1635    rtems_status_code rc = RTEMS_SUCCESSFUL;
1636
1637    if (bd_buf == NULL)
1638        return RTEMS_INVALID_ADDRESS;
1639   
1640    DISABLE_PREEMPTION(key);
1641
1642    if (!bd_buf->modified)
1643    {
1644        bdbuf_initialize_transfer_sema(bd_buf);
1645    }
1646    bd_buf->modified = TRUE;
1647    bd_buf->actual = TRUE;
1648
1649    rc = bdbuf_release(bd_buf);
1650
1651    if (rc == RTEMS_SUCCESSFUL)
1652    {
1653        _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
1654                          WATCHDOG_NO_TIMEOUT, level);
1655    }
1656   
1657    ENABLE_PREEMPTION(key);
1658   
1659    return rc;
1660}
1661
1662/* rtems_bdbuf_syncdev --
1663 *     Synchronize with disk all buffers containing the blocks belonging to
1664 *     specified device.
1665 *
1666 * PARAMETERS:
1667 *     dev - block device number
1668 *
1669 * RETURNS:
1670 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
1671 *     or error code if error is occured)
1672 */
1673rtems_status_code
1674rtems_bdbuf_syncdev(dev_t dev)
1675{
1676    preemption_key key;
1677    ISR_Level level;
1678           
1679    bdbuf_buffer *bd_buf;
1680    disk_device *dd;
1681    bdbuf_pool  *pool;
1682   
1683    dd = rtems_disk_lookup(dev);
1684    if (dd == NULL)
1685        return RTEMS_INVALID_ID;
1686   
1687    pool = bd_ctx.pool + dd->pool;
1688       
1689    DISABLE_PREEMPTION(key);
1690    do {
1691        bd_buf = avl_search_for_sync(&pool->tree, dd);
1692        if (bd_buf != NULL /* && bd_buf->modified */)
1693        {
1694            _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE,
1695                              WATCHDOG_NO_TIMEOUT, level);
1696        }
1697    } while (bd_buf != NULL);
1698    ENABLE_PREEMPTION(key);
1699    return rtems_disk_release(dd);
1700}
1701
1702/* bdbuf_swapout_task --
1703 *     Body of task which take care on flushing modified buffers to the
1704 *     disk.
1705 */
1706static rtems_task
1707bdbuf_swapout_task(rtems_task_argument unused)
1708{
1709    rtems_status_code rc;
1710    int result;
1711    ISR_Level level;
1712    bdbuf_buffer *bd_buf;
1713    bdbuf_pool *bd_pool;
1714    disk_device *dd;
1715    blkdev_request1 req;
1716
1717    while (1)
1718    {
1719        rc = rtems_semaphore_obtain(bd_ctx.flush_sema, RTEMS_WAIT, 0);
1720        if (rc != RTEMS_SUCCESSFUL)
1721        {
1722            rtems_fatal_error_occurred(BLKDEV_FATAL_BDBUF_SWAPOUT);
1723        }
1724           
1725        bd_buf = (bdbuf_buffer *)Chain_Get(&bd_ctx.mod);
1726        if (bd_buf == NULL)
1727        {
1728            /* It is possible that flush_sema semaphore will be released, but
1729             * buffer to be removed from mod chain before swapout task start
1730             * its processing. */
1731            continue;
1732        }
1733
1734        bd_buf->in_progress = TRUE;
1735        bd_buf->use_count++;
1736        bd_pool = bd_ctx.pool + bd_buf->pool;
1737        dd = rtems_disk_lookup(bd_buf->dev);
1738
1739        req.req.req = BLKDEV_REQ_WRITE;
1740        req.req.req_done = bdbuf_write_transfer_done;
1741        req.req.done_arg = bd_buf;
1742        req.req.start = bd_buf->block + dd->start;
1743        req.req.count = 1;
1744        req.req.bufnum = 1;
1745        req.req.bufs[0].length = dd->block_size;
1746        req.req.bufs[0].buffer = bd_buf->buffer;
1747
1748        /* transfer_sema initialized when bd_buf inserted in the mod chain
1749           first time */
1750        result = dd->ioctl(dd->phys_dev->dev, BLKIO_REQUEST, &req);
1751       
1752        rtems_disk_release(dd);
1753       
1754        if (result == -1)
1755        {
1756            bd_buf->status = RTEMS_IO_ERROR;
1757            bd_buf->error = errno;
1758            /* Release tasks waiting on syncing this buffer */
1759            _CORE_mutex_Flush(&bd_buf->transfer_sema, NULL,
1760                              CORE_MUTEX_STATUS_SUCCESSFUL);
1761        }
1762        else
1763        {
1764            if (bd_buf->in_progress)
1765            {
1766                _CORE_mutex_Seize(&bd_buf->transfer_sema, 0, TRUE, 0, level);
1767            }
1768        }
1769        bd_buf->use_count--;
1770
1771        /* Another task have chance to use this buffer, or even
1772         * modify it. If buffer is not in use, insert it in appropriate chain
1773         * and release semaphore */
1774        if (bd_buf->use_count == 0)
1775        {
1776            if (bd_buf->modified)
1777            {
1778                Chain_Append(&bd_ctx.mod, &bd_buf->link);
1779                rc = rtems_semaphore_release(bd_ctx.flush_sema);
1780            }
1781            else
1782            {
1783                Chain_Append(&bd_pool->lru, &bd_buf->link);
1784                rc = rtems_semaphore_release(bd_pool->bufget_sema);
1785            }
1786        }
1787    }
1788}
1789
1790/* rtems_bdbuf_find_pool --
1791 *     Find first appropriate buffer pool. This primitive returns the index
1792 *     of first buffer pool which block size is greater than or equal to
1793 *     specified size.
1794 *
1795 * PARAMETERS:
1796 *     block_size - requested block size
1797 *     pool       - placeholder for result
1798 *
1799 * RETURNS:
1800 *     RTEMS status code: RTEMS_SUCCESSFUL if operation completed successfully,
1801 *     RTEMS_INVALID_SIZE if specified block size is invalid (not a power
1802 *     of 2), RTEMS_NOT_DEFINED if buffer pool for this or greater block size
1803 *     is not configured.
1804 */
1805rtems_status_code
1806rtems_bdbuf_find_pool(int block_size, rtems_bdpool_id *pool)
1807{
1808    rtems_bdpool_id i;
1809    bdbuf_pool *p;
1810    int cursize = INT_MAX;
1811    rtems_bdpool_id curid = -1;
1812    rtems_boolean found = FALSE;
1813    int j;
1814   
1815    for (j = block_size; (j != 0) && ((j & 1) == 0); j >>= 1);
1816    if (j != 1)
1817        return RTEMS_INVALID_SIZE;
1818   
1819    for (i = 0, p = bd_ctx.pool; i < bd_ctx.npools; i++, p++)
1820    {
1821        if ((p->blksize >= block_size) &&
1822            (p->blksize < cursize))
1823        {
1824            curid = i;
1825            cursize = p->blksize;
1826            found = TRUE;
1827        }
1828    }
1829   
1830    if (found)
1831    {
1832        if (pool != NULL)
1833            *pool = curid;
1834        return RTEMS_SUCCESSFUL;
1835    }
1836    else
1837    {
1838        return RTEMS_NOT_DEFINED;
1839    }
1840}
1841
1842/* rtems_bdbuf_get_pool_info --
1843 *     Obtain characteristics of buffer pool with specified number.
1844 *
1845 * PARAMETERS:
1846 *     pool       - buffer pool number
1847 *     block_size - block size for which buffer pool is configured returned
1848 *                  there
1849 *     blocks     - number of buffers in buffer pool returned there
1850 *
1851 * RETURNS:
1852 *     RTEMS status code: RTEMS_SUCCESSFUL if operation completed successfully,
1853 *     RTEMS_INVALID_NUMBER if appropriate buffer pool is not configured.
1854 *
1855 * NOTE:
1856 *     Buffer pools enumerated contiguously starting from 0.
1857 */
1858rtems_status_code
1859rtems_bdbuf_get_pool_info(rtems_bdpool_id pool, int *block_size,
1860                          int *blocks)
1861{
1862    if (pool >= bd_ctx.npools)
1863        return RTEMS_INVALID_NUMBER;
1864   
1865    if (block_size != NULL)
1866    {
1867        *block_size = bd_ctx.pool[pool].blksize;
1868    }
1869   
1870    if (blocks != NULL)
1871    {
1872        *blocks = bd_ctx.pool[pool].nblks;
1873    }
1874   
1875    return RTEMS_SUCCESSFUL;
1876}
Note: See TracBrowser for help on using the repository browser.