Subversion Repositories HelenOS

Rev

Rev 2881 | Rev 2889 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2008 Jakub Jermar
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup fs
  30.  * @{
  31.  */
  32.  
  33. /**
  34.  * @file    fat_idx.c
  35.  * @brief   Layer for translating FAT entities to VFS node indices.
  36.  */
  37.  
  38. #include "fat.h"
  39. #include "../../vfs/vfs.h"
  40. #include <errno.h>
  41. #include <string.h>
  42. #include <libadt/hash_table.h>
  43. #include <libadt/list.h>
  44. #include <assert.h>
  45. #include <futex.h>
  46.  
  47. /** Each instance of this type describes one interval of freed VFS indices. */
  48. typedef struct {
  49.     link_t      link;
  50.     fs_index_t  first;
  51.     fs_index_t  last;
  52. } freed_t;
  53.  
  54. /**
  55.  * Each instance of this type describes state of all VFS indices that
  56.  * are currently unused.
  57.  */
  58. typedef struct {
  59.     link_t      link;
  60.     dev_handle_t    dev_handle;
  61.  
  62.     /** Next unassigned index. */
  63.     fs_index_t  next;
  64.     /** Number of remaining unassigned indices. */
  65.     uint64_t    remaining;
  66.  
  67.     /** Sorted list of intervals of freed indices. */
  68.     link_t      freed_head;
  69. } unused_t;
  70.  
  71. static LIST_INITIALIZE(unused_head);
  72.  
  73. /** Allocate a VFS index which is not currently in use. */
  74. static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
  75. {
  76.     link_t *l;
  77.     unused_t *u;
  78.    
  79.     assert(index);
  80.     for (l = unused_head.next; l != &unused_head; l = l->next) {
  81.         u = list_get_instance(l, unused_t, link);
  82.         if (u->dev_handle == dev_handle)
  83.             goto hit;
  84.     }
  85.  
  86.     /* dev_handle not found */
  87.     return false;  
  88.  
  89. hit:
  90.     if (list_empty(&u->freed_head)) {
  91.         if (u->remaining) {
  92.             /*
  93.              * There are no freed indices, allocate one directly
  94.              * from the counter.
  95.              */
  96.             *index = u->next++;
  97.             --u->remaining;
  98.             return true;
  99.         }
  100.     } else {
  101.         /* There are some freed indices which we can reuse. */
  102.         freed_t *f = list_get_instance(u->freed_head.next, freed_t,
  103.             link);
  104.         *index = f->first;
  105.         if (f->first++ == f->last) {
  106.             /* Destroy the interval. */
  107.             list_remove(&f->link);
  108.             free(f);
  109.         }
  110.         return true;
  111.     }
  112.     /*
  113.      * We ran out of indices, which is extremely unlikely with FAT16, but
  114.      * theoretically still possible (e.g. too many open unlinked nodes or
  115.      * too many zero-sized nodes).
  116.      */
  117.     return false;
  118. }
  119.  
  120. /** If possible, coalesce two intervals of freed indices. */
  121. static void try_coalesce_intervals(link_t *l, link_t *r, link_t *cur)
  122. {
  123.     freed_t *fl = list_get_instance(l, freed_t, link);
  124.     freed_t *fr = list_get_instance(r, freed_t, link);
  125.  
  126.     if (fl->last + 1 == fr->first) {
  127.         if (cur == l) {
  128.             fl->last = fr->last;
  129.             list_remove(r);
  130.             free(r);
  131.         } else {
  132.             fr->first = fl->first;
  133.             list_remove(l);
  134.             free(l);
  135.         }
  136.     }
  137. }
  138.  
  139. /** Free a VFS index, which is no longer in use. */
  140. static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
  141. {
  142.     link_t *l;
  143.     unused_t *u;
  144.  
  145.     for (l = unused_head.next; l != &unused_head; l = l->next) {
  146.         u = list_get_instance(l, unused_t, link);
  147.         if (u->dev_handle == dev_handle)
  148.             goto hit;
  149.     }
  150.  
  151.     /* should not happen */
  152.     assert(0);
  153.  
  154. hit:
  155.     if (u->next == index + 1) {
  156.         /* The index can be returned directly to the counter. */
  157.         u->next--;
  158.         u->remaining++;
  159.         return;
  160.     } else {
  161.         /*
  162.          * The index must be returned either to an existing freed
  163.          * interval or a new interval must be created.
  164.          */
  165.         link_t *lnk;
  166.         freed_t *n;
  167.         for (lnk = u->freed_head.next; lnk != &u->freed_head;
  168.             lnk = lnk->next) {
  169.             freed_t *f = list_get_instance(lnk, freed_t, link);
  170.             if (f->first == index + 1) {
  171.                 f->first--;
  172.                 if (lnk->prev != &u->freed_head)
  173.                     try_coalesce_intervals(lnk->prev, lnk,
  174.                         lnk);
  175.                 return;
  176.             }
  177.             if (f->last == index - 1) {
  178.                 f->last++;
  179.                 if (lnk->next != &u->freed_head)
  180.                     try_coalesce_intervals(lnk, lnk->next,
  181.                         lnk);
  182.                 return;
  183.             }
  184.             if (index > f->first) {
  185.                 n = malloc(sizeof(freed_t));
  186.                 /* TODO: sleep until allocation succeeds */
  187.                 assert(n);
  188.                 link_initialize(&n->link);
  189.                 n->first = index;
  190.                 n->last = index;
  191.                 list_insert_before(&n->link, lnk);
  192.                 return;
  193.             }
  194.  
  195.         }
  196.         /* The index will form the last interval. */
  197.         n = malloc(sizeof(freed_t));
  198.         /* TODO: sleep until allocation succeeds */
  199.         assert(n);
  200.         link_initialize(&n->link);
  201.         n->first = index;
  202.         n->last = index;
  203.         list_append(&n->link, &u->freed_head);
  204.     }
  205. }
  206.  
  207. fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
  208. {
  209.     return NULL;    /* TODO */
  210. }
  211.