qemu/roms/openbios/fs/hfsplus/hfsp_btree.c

   1 /*
   2  * libhfs - library for reading and writing Macintosh HFS volumes
   3  * The fucntions are used to handle the various forms of btrees
   4  * found on HFS+ volumes.
   5  *
   6  * The fucntions are used to handle the various forms of btrees
   7  * found on HFS+ volumes.
   8  *
   9  * Copyright (C) 2000 Klaus Halfmann <khalfmann@libra.de>
  10  * Original 1996-1998 Robert Leslie <rob@mars.org>
  11  * Additional work by  Brad Boyer (flar@pants.nu)
  12  *
  13  * This program is free software; you can redistribute it and/or modify
  14  * it under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version 2 of the License, or
  16  * (at your option) any later version.
  17  *
  18  * This program is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with this program; if not, write to the Free Software
  25  * Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  26  * MA 02110-1301, USA.
  27  *
  28  * $Id: btree.c,v 1.14 2000/10/25 05:43:04 hasi Exp $
  29  */
  30
  31 #include "config.h"
  32 #include "libhfsp.h"
  33 #include "volume.h"
  34 #include "btree.h"
  35 #include "record.h"
  36 #include "swab.h"
  37
  38 /* Read the node from the given buffer and swap the bytes.
  39  *
  40  * return pointer after reading the structure
  41  */
  42 static void* btree_readnode(btree_node_desc* node, void *p)
  43 {
  44     node->next      = bswabU32_inc(p);
  45     node->prev      = bswabU32_inc(p);
  46     node->kind      = bswabU8_inc(p);
  47     node->height    = bswabU8_inc(p);
  48     node->num_rec   = bswabU16_inc(p);
  49     node->reserved  = bswabU16_inc(p);
  50     return p;
  51 }
  52
  53 /* read a btree header from the given buffer and swap the bytes.
  54  *
  55  * return pointer after reading the structure
  56  */
  57 static void* btree_readhead(btree_head* head, void *p)
  58 {
  59         UInt32 *q;
  60         head->depth         = bswabU16_inc(p);
  61         head->root          = bswabU32_inc(p);
  62         head->leaf_count    = bswabU32_inc(p);
  63         head->leaf_head     = bswabU32_inc(p);
  64         head->leaf_tail     = bswabU32_inc(p);
  65         head->node_size     = bswabU16_inc(p);
  66         head->max_key_len   = bswabU16_inc(p);
  67         head->node_count    = bswabU32_inc(p);
  68         head->free_nodes    = bswabU32_inc(p);
  69         head->reserved1     = bswabU16_inc(p);
  70         head->clump_size    = bswabU32_inc(p);
  71         head->btree_type    = bswabU8_inc(p);
  72         head->reserved2     = bswabU8_inc(p);
  73         head->attributes    = bswabU32_inc(p);
  74             // skip reserved bytes
  75         q=((UInt32*) p);
  76         // ((UInt32*) p) += 16;
  77         q+=16;
  78         return q;
  79 }
  80
  81 /* Priority of the depth of the node compared to LRU value.
  82  * Should be the average number of keys per node but these vary. */
  83 #define DEPTH_FACTOR    1000
  84
  85 /* Cache size is height of tree + this value
  86  * Really big numbers wont help in case of ls -R
  87  */
  88 #define EXTRA_CACHESIZE 3
  89
  90 /* Not in use by now ... */
  91 #define CACHE_DIRTY 0x0001
  92
  93 /* Intialize cache with default cache Size,
  94  * must call node_cache_close to deallocate memory */
  95 static int node_cache_init(node_cache* cache, btree* tree, int size)
  96 {
  97     int nodebufsize;
  98     char * buf;
  99
 100     cache->size         = size;
 101     cache->currindex    = 0;
 102     nodebufsize = tree->head.node_size + sizeof(node_buf);
 103     buf = malloc(size *(sizeof(node_entry) + nodebufsize));
 104     if (!buf)
 105         return -1;
 106     cache -> nodebufsize = nodebufsize;
 107     cache -> entries = (node_entry*) buf;
 108     cache -> buffers = (char*) &cache->entries[size];
 109     bzero(cache->entries, size*sizeof(node_entry));
 110     return 0;
 111 }
 112
 113 /* Like cache->buffers[i], since size of node_buf is variable */
 114 static inline node_buf* node_buf_get(node_cache* cache, int i)
 115 {
 116     return (node_buf*) (cache->buffers + (i * cache->nodebufsize));
 117 }
 118
 119 /* flush the node at index */
 120 static void node_cache_flush_node(node_cache* cache, int index)
 121 {
 122     // NYI
 123     cache -> entries[index].index = 0;  // invalidate entry
 124 }
 125
 126 static void node_cache_close(node_cache* cache)
 127 {
 128     if (!cache->entries) // not (fully) intialized ?
 129         return;
 130     free(cache->entries);
 131 }
 132
 133 /* Load the cach node indentified by index with
 134  * the node identified by node_index */
 135
 136 static node_buf* node_cache_load_buf
 137     (btree* bt, node_cache* cache, int index, UInt16 node_index)
 138 {
 139     node_buf    *result     = node_buf_get(cache ,index);
 140     UInt32      blkpernode  = bt->blkpernode;
 141     UInt32      block       = node_index * blkpernode;
 142     void*       p           = volume_readfromfork(bt->vol, result->node, bt->fork,
 143                              block, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
 144     node_entry  *e          = &cache->entries[index];
 145
 146     if (!p)
 147         return NULL;    // evil ...
 148
 149     result->index   = node_index;
 150     btree_readnode(&result->desc, p);
 151
 152     e -> priority   = result->desc.height * DEPTH_FACTOR;
 153     e -> index      = node_index;
 154     return result;
 155 }
 156
 157 /* Read node at given index, using cache.
 158  */
 159 node_buf* btree_node_by_index(btree* bt, UInt16 index)
 160 {
 161     node_cache* cache = &bt->cache;
 162     int         oldindex, lruindex;
 163     int         currindex = cache->currindex;
 164     UInt32      prio;
 165     node_entry  *e;
 166
 167     // Shortcut acces to current node, will not change priorities
 168     if (cache->entries[currindex].index == index)
 169         return node_buf_get(cache ,currindex);
 170     oldindex = currindex;
 171     if (currindex == 0)
 172         currindex = cache->size;
 173     currindex--;
 174     lruindex = oldindex;            // entry to be flushed when needed
 175     prio     = 0;                   // current priority
 176     while (currindex != oldindex)   // round robin
 177     {
 178         e = &cache->entries[currindex];
 179         if (e->index == index)      // got it
 180         {
 181             if (e->priority != 0)   // already top, uuh
 182                 e->priority--;
 183             cache->currindex = currindex;
 184             return node_buf_get(cache ,currindex);
 185         }
 186         else
 187         {
 188             if (!e->index)
 189             {
 190                 lruindex = currindex;
 191                 break;  // empty entry, load it
 192             }
 193             if (e->priority != UINT_MAX) // already least, uuh
 194                 e->priority++;
 195         }
 196         if (prio < e->priority)
 197         {
 198             lruindex = currindex;
 199             prio = e->priority;
 200         }
 201         if (currindex == 0)
 202             currindex = cache->size;
 203         currindex--;
 204     }
 205     e = &cache->entries[lruindex];
 206     cache->currindex = lruindex;
 207     if (e->flags & CACHE_DIRTY)
 208            node_cache_flush_node(    cache, lruindex);
 209     return node_cache_load_buf  (bt, cache, lruindex, index);
 210 }
 211
 212 /** intialize the btree with the first entry in the fork */
 213 static int btree_init(btree* bt, volume* vol, hfsp_fork_raw* fork)
 214 {
 215     void            *p;
 216     char            buf[vol->blksize];
 217     UInt16          node_size;
 218     btree_node_desc node;
 219
 220     bt->vol     = vol;
 221     bt->fork    = fork;
 222     p   = volume_readfromfork(vol, buf, fork, 0, 1,
 223                  HFSP_EXTENT_DATA, bt->cnid);
 224     if (!p)
 225         return -1;
 226     p = btree_readnode(&node, p);
 227     if (node.kind != HFSP_NODE_HEAD)
 228         return -1;   // should not happen ?
 229     btree_readhead(&bt->head, p);
 230
 231     node_size = bt->head.node_size;
 232     bt->blkpernode = node_size / vol->blksize;
 233
 234     if (bt->blkpernode == 0 || vol->blksize *
 235             bt->blkpernode != node_size)
 236         return -1;  // should never happen ...
 237
 238     node_cache_init(&bt->cache, bt, bt->head.depth + EXTRA_CACHESIZE);
 239
 240     // Allocate buffer
 241     // bt->buf = malloc(node_size);
 242     // if (!bt->buf)
 243     //  return ENOMEM;
 244
 245     return 0;
 246 }
 247
 248 /** Intialize catalog btree, so that btree_close can safely be called. */
 249 void btree_reset(btree* bt)
 250 {
 251     bt->cache.entries = NULL;
 252 }
 253
 254 /** Intialize catalog btree */
 255 int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork)
 256 {
 257     int result = btree_init(bt,vol,fork);       // super (...)
 258     bt->cnid  = HFSP_CAT_CNID;
 259     bt->kcomp = record_key_compare;
 260     bt->kread = record_readkey;
 261     return result;
 262 }
 263
 264 /** Intialize catalog btree */
 265 int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork)
 266 {
 267     int result = btree_init(bt,vol,fork);       // super (...)
 268     bt->cnid  = HFSP_EXT_CNID;
 269     bt->kcomp = record_extent_key_compare;
 270     bt->kread = record_extent_readkey;
 271     return result;
 272 }
 273
 274 /** close the btree and free any resources */
 275 void btree_close(btree* bt)
 276 {
 277     node_cache_close(&bt->cache);
 278     // free(bt->buf);
 279 }
 280
 281 /* returns pointer to key given by index in current node.
 282  *
 283  * Assumes that current node is not NODE_HEAD ...
 284  */
 285 void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index)
 286 {
 287     UInt16  node_size       = bt->head.node_size;
 288         // The offsets are found at the end of the node ...
 289     UInt16  off_pos         = node_size - (index +1) * sizeof(btree_record_offset);
 290         // position of offset at end of node
 291     btree_record_offset* offset =
 292         (btree_record_offset*) (buf->node + off_pos);
 293
 294     // now we have the offset and can read the key ...
 295 #ifdef CONFIG_LITTLE_ENDIAN
 296     return buf->node + bswabU16(*offset);
 297 #else
 298     return buf->node + *offset;
 299 #endif
 300 }
 301
 302
 303 #ifdef DEBUG
 304
 305 /* print btree header node information */
 306 void btree_printhead(btree_head* head)
 307 {
 308     UInt32 attr;
 309     printf("  depth       : %#X\n",  head->depth);
 310     printf("  root        : %#lX\n", head->root);
 311     printf("  leaf_count  : %#lX\n", head->leaf_count);
 312     printf("  leaf_head   : %#lX\n", head->leaf_head);
 313     printf("  leaf_tail   : %#lX\n", head->leaf_tail);
 314     printf("  node_size   : %#X\n",  head->node_size);
 315     printf("  max_key_len : %#X\n",  head->max_key_len);
 316     printf("  node_count  : %#lX\n", head->node_count);
 317     printf("  free_nodes  : %#lX\n", head->free_nodes);
 318     printf("  reserved1   : %#X\n",  head->reserved1);
 319     printf("  clump_size  : %#lX\n", head->clump_size);
 320     printf("  btree_type  : %#X\n",  head->btree_type);
 321     attr = head->attributes;
 322     printf("  reserved2   : %#X\n",  head->reserved2);
 323     if (attr & HFSPLUS_BAD_CLOSE)
 324         printf(" HFSPLUS_BAD_CLOSE *** ");
 325     else
 326         printf(" !HFSPLUS_BAD_CLOSE");
 327     if (attr & HFSPLUS_TREE_BIGKEYS)
 328         printf(" HFSPLUS_TREE_BIGKEYS ");
 329     else
 330         printf("  !HFSPLUS_TREE_BIGKEYS");
 331     if (attr & HFSPLUS_TREE_VAR_NDXKEY_SIZE)
 332         printf(" HFSPLUS_TREE_VAR_NDXKEY_SIZE");
 333     else
 334         printf(" !HFSPLUS_TREE_VAR_NDXKEY_SIZE");
 335     if (attr & HFSPLUS_TREE_UNUSED)
 336         printf(" HFSPLUS_TREE_UNUSED ***\n");
 337     printf("\n");
 338 }
 339
 340 /* Dump all the node information to stdout */
 341 void btree_print(btree* bt)
 342 {
 343     btree_node_desc* node;
 344
 345     btree_printhead(&bt->head);
 346
 347     node = &bt->node;
 348     printf("next     : %#lX\n", node->next);
 349     printf("prev     : %#lX\n", node->prev);
 350     printf("height   : %#X\n",  node->height);
 351     printf("num_rec  : %#X\n",  node->num_rec);
 352     printf("reserved : %#X\n",  node->reserved);
 353     printf("height   : %#X\n",  node->height);                                      switch(node->kind)
 354     {
 355         case HFSP_NODE_NDX  :
 356             printf("HFSP_NODE_NDX\n");
 357             break;
 358         case HFSP_NODE_HEAD :
 359             printf("HFSP_NODE_HEAD\n");
 360             break;
 361         case HFSP_NODE_MAP  :
 362             printf("HFSP_NODE_MAP\n");
 363             break;
 364         case HFSP_NODE_LEAF :
 365             printf("HFSP_NODE_LEAF\n");
 366             break;
 367         default:
 368             printf("*** Unknown Node type ***\n");
 369     }
 370 }
 371
 372 #endif