Subversion Repositories HelenOS

Rev

Rev 3615 | Rev 3638 | 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_index_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_index_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. static fat_idx_t *fat_idx_create(dev_handle_t dev_handle)
  342. {
  343.     fat_idx_t *fidx;
  344.  
  345.     fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
  346.     if (!fidx)
  347.         return NULL;
  348.     if (!fat_index_alloc(dev_handle, &fidx->index)) {
  349.         free(fidx);
  350.         return NULL;
  351.     }
  352.        
  353.     link_initialize(&fidx->uph_link);
  354.     link_initialize(&fidx->uih_link);
  355.     futex_initialize(&fidx->lock, 1);
  356.     fidx->dev_handle = dev_handle;
  357.     fidx->pfc = FAT_CLST_RES0;  /* no parent yet */
  358.     fidx->pdi = 0;
  359.     fidx->nodep = NULL;
  360.  
  361.     return fidx;
  362. }
  363.  
  364. fat_idx_t *fat_idx_get_new(dev_handle_t dev_handle)
  365. {
  366.     fat_idx_t *fidx;
  367.  
  368.     futex_down(&used_futex);
  369.     fidx = fat_idx_create(dev_handle);
  370.     if (!fidx) {
  371.         futex_up(&used_futex);
  372.         return NULL;
  373.     }
  374.        
  375.     unsigned long ikey[] = {
  376.         [UIH_DH_KEY] = dev_handle,
  377.         [UIH_INDEX_KEY] = fidx->index,
  378.     };
  379.    
  380.     hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
  381.     futex_down(&fidx->lock);
  382.     futex_up(&used_futex);
  383.  
  384.     return fidx;
  385. }
  386.  
  387. fat_idx_t *
  388. fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
  389. {
  390.     fat_idx_t *fidx;
  391.     link_t *l;
  392.     unsigned long pkey[] = {
  393.         [UPH_DH_KEY] = dev_handle,
  394.         [UPH_PFC_KEY] = pfc,
  395.         [UPH_PDI_KEY] = pdi,
  396.     };
  397.  
  398.     futex_down(&used_futex);
  399.     l = hash_table_find(&up_hash, pkey);
  400.     if (l) {
  401.         fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
  402.     } else {
  403.         fidx = fat_idx_create(dev_handle);
  404.         if (!fidx) {
  405.             futex_up(&used_futex);
  406.             return NULL;
  407.         }
  408.        
  409.         unsigned long ikey[] = {
  410.             [UIH_DH_KEY] = dev_handle,
  411.             [UIH_INDEX_KEY] = fidx->index,
  412.         };
  413.    
  414.         fidx->pfc = pfc;
  415.         fidx->pdi = pdi;
  416.  
  417.         hash_table_insert(&up_hash, pkey, &fidx->uph_link);
  418.         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
  419.     }
  420.     futex_down(&fidx->lock);
  421.     futex_up(&used_futex);
  422.  
  423.     return fidx;
  424. }
  425.  
  426. void fat_idx_hashin(fat_idx_t *idx)
  427. {
  428.     unsigned long pkey[] = {
  429.         [UPH_DH_KEY] = idx->dev_handle,
  430.         [UPH_PFC_KEY] = idx->pfc,
  431.         [UPH_PDI_KEY] = idx->pdi,
  432.     };
  433.  
  434.     futex_down(&used_futex);
  435.     hash_table_insert(&up_hash, pkey, &idx->uph_link);
  436.     futex_up(&used_futex);
  437. }
  438.  
  439. fat_idx_t *
  440. fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
  441. {
  442.     fat_idx_t *fidx = NULL;
  443.     link_t *l;
  444.     unsigned long ikey[] = {
  445.         [UIH_DH_KEY] = dev_handle,
  446.         [UIH_INDEX_KEY] = index,
  447.     };
  448.  
  449.     futex_down(&used_futex);
  450.     l = hash_table_find(&ui_hash, ikey);
  451.     if (l) {
  452.         fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
  453.         futex_down(&fidx->lock);
  454.     }
  455.     futex_up(&used_futex);
  456.  
  457.     return fidx;
  458. }
  459.  
  460. /** Destroy the index structure.
  461.  *
  462.  * @param idx       The index structure to be destroyed.
  463.  */
  464. void fat_idx_destroy(fat_idx_t *idx)
  465. {
  466.     unsigned long ikey[] = {
  467.         [UIH_DH_KEY] = idx->dev_handle,
  468.         [UIH_INDEX_KEY] = idx->index,
  469.     };
  470.  
  471.     assert(idx->pfc == FAT_CLST_RES0);
  472.  
  473.     futex_down(&used_futex);
  474.     /*
  475.      * Since we can only free unlinked nodes, the index structure is not
  476.      * present in the position hash (uph). We therefore hash it out from
  477.      * the index hash only.
  478.      */
  479.     hash_table_remove(&ui_hash, ikey, 2);
  480.     futex_up(&used_futex);
  481.     /* Release the VFS index. */
  482.     fat_index_free(idx->dev_handle, idx->index);
  483.     /* Deallocate the structure. */
  484.     free(idx);
  485. }
  486.  
  487. int fat_idx_init(void)
  488. {
  489.     if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
  490.         return ENOMEM;
  491.     if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
  492.         hash_table_destroy(&up_hash);
  493.         return ENOMEM;
  494.     }
  495.     return EOK;
  496. }
  497.  
  498. void fat_idx_fini(void)
  499. {
  500.     /* We assume the hash tables are empty. */
  501.     hash_table_destroy(&up_hash);
  502.     hash_table_destroy(&ui_hash);
  503. }
  504.  
  505. int fat_idx_init_by_dev_handle(dev_handle_t dev_handle)
  506. {
  507.     unused_t *u;
  508.     int rc = EOK;
  509.  
  510.     u = (unused_t *) malloc(sizeof(unused_t));
  511.     if (!u)
  512.         return ENOMEM;
  513.     unused_initialize(u, dev_handle);
  514.     futex_down(&unused_futex);
  515.     if (!unused_find(dev_handle, false))
  516.         list_append(&u->link, &unused_head);
  517.     else
  518.         rc = EEXIST;
  519.     futex_up(&unused_futex);
  520.     return rc;
  521. }
  522.  
  523. void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
  524. {
  525.     unused_t *u;
  526.  
  527.     u = unused_find(dev_handle, true);
  528.     assert(u);
  529.     list_remove(&u->link);
  530.     futex_up(&unused_futex);
  531.  
  532.     while (!list_empty(&u->freed_head)) {
  533.         freed_t *f;
  534.         f = list_get_instance(u->freed_head.next, freed_t, link);
  535.         list_remove(&f->link);
  536.         free(f);
  537.     }
  538.     free(u);
  539. }
  540.  
  541. /**
  542.  * @}
  543.  */
  544.