Subversion Repositories HelenOS

Rev

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