Subversion Repositories HelenOS

Rev

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