Subversion Repositories HelenOS

Rev

Rev 2951 | Rev 3111 | 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. /** Futex protecting the list of unused structures. */
  72. static futex_t unused_futex = FUTEX_INITIALIZER;
  73.  
  74. /** List of unused structures. */
  75. static LIST_INITIALIZE(unused_head);
  76.  
  77. static void unused_initialize(unused_t *u, dev_handle_t dev_handle)
  78. {
  79.     link_initialize(&u->link);
  80.     u->dev_handle = dev_handle;
  81.     u->next = 0;
  82.     u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
  83.     list_initialize(&u->freed_head);
  84. }
  85.  
  86. /** Futex protecting the up_hash and ui_hash. */
  87. static futex_t used_futex = FUTEX_INITIALIZER;
  88.  
  89. /**
  90.  * Global hash table of all used fat_idx_t structures.
  91.  * The index structures are hashed by the dev_handle, parent node's first
  92.  * cluster and index within the parent directory.
  93.  */
  94. static hash_table_t up_hash;
  95.  
  96. #define UPH_BUCKETS_LOG 12
  97. #define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
  98.  
  99. #define UPH_DH_KEY  0
  100. #define UPH_PFC_KEY 1
  101. #define UPH_PDI_KEY 2
  102.  
  103. static hash_index_t pos_hash(unsigned long key[])
  104. {
  105.     dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
  106.     fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
  107.     unsigned pdi = (unsigned)key[UPH_PDI_KEY];
  108.  
  109.     hash_index_t h;
  110.  
  111.     /*
  112.      * The least significant half of all bits are the least significant bits
  113.      * of the parent node's first cluster.
  114.      *
  115.      * The least significant half of the most significant half of all bits
  116.      * are the least significant bits of the node's dentry index within the
  117.      * parent directory node.
  118.      *
  119.      * The most significant half of the most significant half of all bits
  120.      * are the least significant bits of the device handle.
  121.      */
  122.     h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
  123.     h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
  124.         (UPH_BUCKETS_LOG / 2);
  125.     h |= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
  126.         (3 * (UPH_BUCKETS_LOG / 4));
  127.  
  128.     return h;
  129. }
  130.  
  131. static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
  132. {
  133.     dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
  134.     fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
  135.     unsigned pdi = (unsigned)key[UPH_PDI_KEY];
  136.     fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
  137.  
  138.     return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
  139.         (pdi == fidx->pdi);
  140. }
  141.  
  142. static void pos_remove_callback(link_t *item)
  143. {
  144.     /* nothing to do */
  145. }
  146.  
  147. static hash_table_operations_t uph_ops = {
  148.     .hash = pos_hash,
  149.     .compare = pos_compare,
  150.     .remove_callback = pos_remove_callback,
  151. };
  152.  
  153. /**
  154.  * Global hash table of all used fat_idx_t structures.
  155.  * The index structures are hashed by the dev_handle and index.
  156.  */
  157. static hash_table_t ui_hash;
  158.  
  159. #define UIH_BUCKETS_LOG 12
  160. #define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
  161.  
  162. #define UIH_DH_KEY  0
  163. #define UIH_INDEX_KEY   1
  164.  
  165. static hash_index_t idx_hash(unsigned long key[])
  166. {
  167.     dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
  168.     fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
  169.  
  170.     hash_index_t h;
  171.  
  172.     h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
  173.     h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
  174.         (UIH_BUCKETS_LOG / 2);
  175.  
  176.     return h;
  177. }
  178.  
  179. static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
  180. {
  181.     dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
  182.     fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
  183.     fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
  184.  
  185.     return (dev_handle == fidx->dev_handle) && (index == fidx->index);
  186. }
  187.  
  188. static void idx_remove_callback(link_t *item)
  189. {
  190.     /* nothing to do */
  191. }
  192.  
  193. static hash_table_operations_t uih_ops = {
  194.     .hash = idx_hash,
  195.     .compare = idx_compare,
  196.     .remove_callback = idx_remove_callback,
  197. };
  198.  
  199. /** Allocate a VFS index which is not currently in use. */
  200. static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
  201. {
  202.     link_t *l;
  203.     unused_t *u;
  204.    
  205.     assert(index);
  206.     futex_down(&unused_futex);
  207.     for (l = unused_head.next; l != &unused_head; l = l->next) {
  208.         u = list_get_instance(l, unused_t, link);
  209.         if (u->dev_handle == dev_handle)
  210.             goto hit;
  211.     }
  212.     futex_up(&unused_futex);
  213.    
  214.     /* dev_handle not found */
  215.     return false;  
  216.  
  217. hit:
  218.     if (list_empty(&u->freed_head)) {
  219.         if (u->remaining) {
  220.             /*
  221.              * There are no freed indices, allocate one directly
  222.              * from the counter.
  223.              */
  224.             *index = u->next++;
  225.             --u->remaining;
  226.             futex_up(&unused_futex);
  227.             return true;
  228.         }
  229.     } else {
  230.         /* There are some freed indices which we can reuse. */
  231.         freed_t *f = list_get_instance(u->freed_head.next, freed_t,
  232.             link);
  233.         *index = f->first;
  234.         if (f->first++ == f->last) {
  235.             /* Destroy the interval. */
  236.             list_remove(&f->link);
  237.             free(f);
  238.         }
  239.         futex_up(&unused_futex);
  240.         return true;
  241.     }
  242.     /*
  243.      * We ran out of indices, which is extremely unlikely with FAT16, but
  244.      * theoretically still possible (e.g. too many open unlinked nodes or
  245.      * too many zero-sized nodes).
  246.      */
  247.     futex_up(&unused_futex);
  248.     return false;
  249. }
  250.  
  251. /** If possible, coalesce two intervals of freed indices. */
  252. static void try_coalesce_intervals(link_t *l, link_t *r, link_t *cur)
  253. {
  254.     freed_t *fl = list_get_instance(l, freed_t, link);
  255.     freed_t *fr = list_get_instance(r, freed_t, link);
  256.  
  257.     if (fl->last + 1 == fr->first) {
  258.         if (cur == l) {
  259.             fl->last = fr->last;
  260.             list_remove(r);
  261.             free(r);
  262.         } else {
  263.             fr->first = fl->first;
  264.             list_remove(l);
  265.             free(l);
  266.         }
  267.     }
  268. }
  269.  
  270. /** Free a VFS index, which is no longer in use. */
  271. static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
  272. {
  273.     link_t *l;
  274.     unused_t *u;
  275.  
  276.     futex_down(&unused_futex);
  277.     for (l = unused_head.next; l != &unused_head; l = l->next) {
  278.         u = list_get_instance(l, unused_t, link);
  279.         if (u->dev_handle == dev_handle)
  280.             goto hit;
  281.     }
  282.     futex_up(&unused_futex);
  283.  
  284.     /* should not happen */
  285.     assert(0);
  286.  
  287. hit:
  288.     if (u->next == index + 1) {
  289.         /* The index can be returned directly to the counter. */
  290.         u->next--;
  291.         u->remaining++;
  292.     } else {
  293.         /*
  294.          * The index must be returned either to an existing freed
  295.          * interval or a new interval must be created.
  296.          */
  297.         link_t *lnk;
  298.         freed_t *n;
  299.         for (lnk = u->freed_head.next; lnk != &u->freed_head;
  300.             lnk = lnk->next) {
  301.             freed_t *f = list_get_instance(lnk, freed_t, link);
  302.             if (f->first == index + 1) {
  303.                 f->first--;
  304.                 if (lnk->prev != &u->freed_head)
  305.                     try_coalesce_intervals(lnk->prev, lnk,
  306.                         lnk);
  307.                 futex_up(&unused_futex);
  308.                 return;
  309.             }
  310.             if (f->last == index - 1) {
  311.                 f->last++;
  312.                 if (lnk->next != &u->freed_head)
  313.                     try_coalesce_intervals(lnk, lnk->next,
  314.                         lnk);
  315.                 futex_up(&unused_futex);
  316.                 return;
  317.             }
  318.             if (index > f->first) {
  319.                 n = malloc(sizeof(freed_t));
  320.                 /* TODO: sleep until allocation succeeds */
  321.                 assert(n);
  322.                 link_initialize(&n->link);
  323.                 n->first = index;
  324.                 n->last = index;
  325.                 list_insert_before(&n->link, lnk);
  326.                 futex_up(&unused_futex);
  327.                 return;
  328.             }
  329.  
  330.         }
  331.         /* The index will form the last interval. */
  332.         n = malloc(sizeof(freed_t));
  333.         /* TODO: sleep until allocation succeeds */
  334.         assert(n);
  335.         link_initialize(&n->link);
  336.         n->first = index;
  337.         n->last = index;
  338.         list_append(&n->link, &u->freed_head);
  339.     }
  340.     futex_up(&unused_futex);
  341. }
  342.  
  343. fat_idx_t *
  344. fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
  345. {
  346.     fat_idx_t *fidx;
  347.     link_t *l;
  348.     unsigned long pkey[] = {
  349.         [UPH_DH_KEY] = dev_handle,
  350.         [UPH_PFC_KEY] = pfc,
  351.         [UPH_PDI_KEY] = pdi,
  352.     };
  353.  
  354.     futex_down(&used_futex);
  355.     l = hash_table_find(&up_hash, pkey);
  356.     if (l) {
  357.         fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
  358.     } else {
  359.         fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
  360.         if (!fidx) {
  361.             futex_up(&used_futex);
  362.             return NULL;
  363.         }
  364.         if (!fat_idx_alloc(dev_handle, &fidx->index)) {
  365.             free(fidx);
  366.             futex_up(&used_futex);
  367.             return NULL;
  368.         }
  369.        
  370.         unsigned long ikey[] = {
  371.             [UIH_DH_KEY] = dev_handle,
  372.             [UIH_INDEX_KEY] = fidx->index,
  373.         };
  374.    
  375.         link_initialize(&fidx->uph_link);
  376.         link_initialize(&fidx->uih_link);
  377.         futex_initialize(&fidx->lock, 1);
  378.         fidx->dev_handle = dev_handle;
  379.         fidx->pfc = pfc;
  380.         fidx->pdi = pdi;
  381.         fidx->nodep = NULL;
  382.  
  383.         hash_table_insert(&up_hash, pkey, &fidx->uph_link);
  384.         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
  385.     }
  386.     futex_down(&fidx->lock);
  387.     futex_up(&used_futex);
  388.  
  389.     return fidx;
  390. }
  391.  
  392. fat_idx_t *
  393. fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
  394. {
  395.     fat_idx_t *fidx = NULL;
  396.     link_t *l;
  397.     unsigned long ikey[] = {
  398.         [UIH_DH_KEY] = dev_handle,
  399.         [UIH_INDEX_KEY] = index,
  400.     };
  401.  
  402.     futex_down(&used_futex);
  403.     l = hash_table_find(&ui_hash, ikey);
  404.     if (l) {
  405.         fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
  406.         futex_down(&fidx->lock);
  407.     }
  408.     futex_up(&used_futex);
  409.  
  410.     return fidx;
  411. }
  412.  
  413. int fat_idx_init(void)
  414. {
  415.     if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
  416.         return ENOMEM;
  417.     if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
  418.         hash_table_destroy(&up_hash);
  419.         return ENOMEM;
  420.     }
  421.     return EOK;
  422. }
  423.  
  424. void fat_idx_fini(void)
  425. {
  426.     /* We assume the hash tables are empty. */
  427.     hash_table_destroy(&up_hash);
  428.     hash_table_destroy(&ui_hash);
  429. }
  430.  
  431. int fat_idx_init_by_dev_handle(dev_handle_t dev_handle)
  432. {
  433.     unused_t *u = (unused_t *) malloc(sizeof(unused_t));
  434.     if (!u)
  435.         return ENOMEM;
  436.     unused_initialize(u, dev_handle);
  437.     futex_down(&unused_futex);
  438.     list_append(&u->link, &unused_head);
  439.     futex_up(&unused_futex);
  440.     return EOK;
  441. }
  442.  
  443. void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
  444. {
  445.     unused_t *u;
  446.     link_t *l;
  447.  
  448.     futex_down(&unused_futex);
  449.     for (l = unused_head.next; l != &unused_head; l = l->next) {
  450.         u = list_get_instance(l, unused_t, link);
  451.         if (u->dev_handle == dev_handle)
  452.             goto hit;
  453.     }
  454.     futex_up(&unused_futex);
  455.  
  456.     assert(false);  /* should not happen */
  457.  
  458. hit:
  459.     list_remove(&u->link);
  460.     futex_up(&unused_futex);
  461.  
  462.     while (!list_empty(&u->freed_head)) {
  463.         freed_t *f;
  464.         f = list_get_instance(u->freed_head.next, freed_t, link);
  465.         list_remove(&f->link);
  466.         free(f);
  467.     }
  468.     free(u);
  469. }
  470.  
  471. /**
  472.  * @}
  473.  */
  474.