sys/vfs/hammer/hammer_alist.h

   1 /*
   2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.h,v 1.2 2007/10/16 18:16:42 dillon Exp $
  35  */
  36
  37 /*
  38  * The structures below represent HAMMER's on-disk and in-memory A-List
  39  * support.  An A-list is a radix tree bitmap allocator with hinting.  It
  40  * is very fast and efficient.
  41  *
  42  * A-lists can be single-layered or multi-layered.  A single-layered
  43  * A-list uses a radix 32 leaf and radix 16 internal nodes.  A multi-layered
  44  * A-list uses a radix 16 leaf and radix 16 internal nodes.
  45  *
  46  * Multi-layered A-lists allow otherwise independant A-lists to be stacked
  47  * to form a single A-list.
  48  */
  49
  50 /*
  51  * This on-disk structure represents the actual information an A-list needs
  52  * to store to disk.  Each A-list layer is made up of a linear array of
  53  * meta-elements.  The number of elements needed is calculated using a
  54  * recursion.  A-lists contain an early-termination feature which allows
  55  * an A-list's storage to scale to the actual number of blocks that need
  56  * to be managed regardless of whether they are on a radix boundary or not.
  57  *
  58  * The first almeta structure in the array is used for housekeeping and not
  59  * part of the topology proper.  The second almeta structure is the 'root'
  60  * meta.
  61  */
  62 typedef struct hammer_almeta {
  63         u_int32_t       bm_bitmap;
  64         int32_t         bm_bighint;
  65 } *hammer_almeta_t;
  66
  67 #define bm_alist_freeblks       bm_bitmap
  68
  69 #define HAMMER_ALMETA_SIZE      8
  70
  71 /*
  72  * This in-memory structure specifies how an a-list is configured and
  73  * can be shared by multiple live alists.
  74  */
  75 typedef struct hammer_alist_config {
  76         int32_t bl_blocks;      /* area of coverage */
  77         int32_t bl_radix;       /* coverage radix */
  78         int32_t bl_base_radix;  /* chain to other allocators */
  79         int32_t bl_skip;        /* starting skip for linear layout */
  80         int32_t bl_rootblks;    /* meta-blocks allocated for tree */
  81         int32_t bl_terminal;    /* terminal alist, else layer recursion */
  82         int     (*bl_radix_init)(void *info, int32_t blk, int32_t radix);
  83         int     (*bl_radix_destroy)(void *info, int32_t blk, int32_t radix);
  84         int32_t (*bl_radix_alloc_fwd)(void *info, int32_t blk, int32_t radix,
  85                                         int32_t count, int32_t atblk,
  86                                         int32_t *fullp);
  87         int32_t (*bl_radix_alloc_rev)(void *info, int32_t blk, int32_t radix,
  88                                         int32_t count, int32_t atblk,
  89                                         int32_t *fullp);
  90         void    (*bl_radix_free)(void *info, int32_t blk, int32_t radix,
  91                                         int32_t base_blk, int32_t count,
  92                                         int32_t *emptyp);
  93         void    (*bl_radix_print)(void *info, int32_t blk, int32_t radix,
  94                                         int tab);
  95 } *hammer_alist_config_t;
  96
  97 /*
  98  * This in-memory structure is needed for each live alist.
  99  */
 100 typedef struct hammer_alist_live {
 101         hammer_alist_config_t config;   /* a-list configuration */
 102         hammer_almeta_t meta;           /* location of meta array */
 103         void *info;                     /* chaining call info argument */
 104 } *hammer_alist_t;
 105
 106 #define HAMMER_ALIST_META_RADIX (sizeof(int32_t) * 4)   /* 16 */
 107 #define HAMMER_ALIST_BMAP_RADIX (sizeof(int32_t) * 8)   /* 32 */
 108 #define HAMMER_ALIST_BLOCK_NONE ((int32_t)-1)
 109 #define HAMMER_ALIST_BLOCK_MAX  ((int32_t)0x7fffffff)
 110
 111 /*
 112  * Hard-code some pre-calculated constants for managing varying numbers
 113  * of blocks.  These are the number of meta-elements required.
 114  */
 115 #define HAMMER_ALIST_METAELMS_256_1LYR  11
 116 #define HAMMER_ALIST_METAELMS_32K_1LYR  1095
 117 #define HAMMER_ALIST_METAELMS_16K_2LYR  HAMMER_ALIST_METAELMS_32K_1LYR
 118
 119 #define HAMMER_ALIST_METAELMS_4K_1LYR   139
 120 #define HAMMER_ALIST_METAELMS_4K_2LYR   275
 121
 122 /*
 123  * Function library support available to kernel and userland
 124  */
 125 void hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
 126                            int32_t base_radix, int32_t maxmeta);
 127 void hammer_alist_init(hammer_alist_t live);
 128 int32_t hammer_alist_alloc(hammer_alist_t live, int32_t count);
 129 int32_t hammer_alist_alloc_fwd(hammer_alist_t live,
 130                            int32_t count, int32_t atblk);
 131 int32_t hammer_alist_alloc_rev(hammer_alist_t live,
 132                            int32_t count, int32_t atblk);
 133 int hammer_alist_isfull(hammer_alist_t live);
 134 int hammer_alist_isempty(hammer_alist_t live);
 135 void hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count);
 136