fs/reiserfs/objectid.c

   1 /*
   2  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3  */
   4
   5 #include <linux/config.h>
   6 #include <linux/string.h>
   7 #include <linux/random.h>
   8 #include <linux/time.h>
   9 #include <linux/reiserfs_fs.h>
  10 #include <linux/reiserfs_fs_sb.h>
  11
  12 // find where objectid map starts
  13 #define objectid_map(s,rs) (old_format_only (s) ? \
  14                          (__u32 *)((struct reiserfs_super_block_v1 *)(rs) + 1) :\
  15                          (__u32 *)((rs) + 1))
  16
  17
  18 #ifdef CONFIG_REISERFS_CHECK
  19
  20 static void check_objectid_map (struct super_block * s, __u32 * map)
  21 {
  22     if (le32_to_cpu (map[0]) != 1)
  23         reiserfs_panic (s, "vs-15010: check_objectid_map: map corrupted: %lx",
  24                         ( long unsigned int ) le32_to_cpu (map[0]));
  25
  26     // FIXME: add something else here
  27 }
  28
  29 #else
  30 static void check_objectid_map (struct super_block * s, __u32 * map)
  31 {;}
  32 #endif
  33
  34
  35 /* When we allocate objectids we allocate the first unused objectid.
  36    Each sequence of objectids in use (the odd sequences) is followed
  37    by a sequence of objectids not in use (the even sequences).  We
  38    only need to record the last objectid in each of these sequences
  39    (both the odd and even sequences) in order to fully define the
  40    boundaries of the sequences.  A consequence of allocating the first
  41    objectid not in use is that under most conditions this scheme is
  42    extremely compact.  The exception is immediately after a sequence
  43    of operations which deletes a large number of objects of
  44    non-sequential objectids, and even then it will become compact
  45    again as soon as more objects are created.  Note that many
  46    interesting optimizations of layout could result from complicating
  47    objectid assignment, but we have deferred making them for now. */
  48
  49
  50 /* get unique object identifier */
  51 __u32 reiserfs_get_unused_objectid (struct reiserfs_transaction_handle *th)
  52 {
  53     struct super_block * s = th->t_super;
  54     struct reiserfs_super_block * rs = SB_DISK_SUPER_BLOCK (s);
  55     __u32 * map = objectid_map (s, rs);
  56     __u32 unused_objectid;
  57
  58
  59     check_objectid_map (s, map);
  60
  61     reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1) ;
  62                                 /* comment needed -Hans */
  63     unused_objectid = le32_to_cpu (map[1]);
  64     if (unused_objectid == U32_MAX) {
  65         reiserfs_warning (s, "%s: no more object ids", __FUNCTION__);
  66         reiserfs_restore_prepared_buffer(s, SB_BUFFER_WITH_SB(s)) ;
  67         return 0;
  68     }
  69
  70     /* This incrementation allocates the first unused objectid. That
  71        is to say, the first entry on the objectid map is the first
  72        unused objectid, and by incrementing it we use it.  See below
  73        where we check to see if we eliminated a sequence of unused
  74        objectids.... */
  75     map[1] = cpu_to_le32 (unused_objectid + 1);
  76
  77     /* Now we check to see if we eliminated the last remaining member of
  78        the first even sequence (and can eliminate the sequence by
  79        eliminating its last objectid from oids), and can collapse the
  80        first two odd sequences into one sequence.  If so, then the net
  81        result is to eliminate a pair of objectids from oids.  We do this
  82        by shifting the entire map to the left. */
  83     if (sb_oid_cursize(rs) > 2 && map[1] == map[2]) {
  84         memmove (map + 1, map + 3, (sb_oid_cursize(rs) - 3) * sizeof(__u32));
  85         set_sb_oid_cursize( rs, sb_oid_cursize(rs) - 2 );
  86     }
  87
  88     journal_mark_dirty(th, s, SB_BUFFER_WITH_SB (s));
  89     return unused_objectid;
  90 }
  91
  92
  93 /* makes object identifier unused */
  94 void reiserfs_release_objectid (struct reiserfs_transaction_handle *th,
  95                                 __u32 objectid_to_release)
  96 {
  97     struct super_block * s = th->t_super;
  98     struct reiserfs_super_block * rs = SB_DISK_SUPER_BLOCK (s);
  99     __u32 * map = objectid_map (s, rs);
 100     int i = 0;
 101
 102     //return;
 103     check_objectid_map (s, map);
 104
 105     reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1) ;
 106     journal_mark_dirty(th, s, SB_BUFFER_WITH_SB (s));
 107
 108     /* start at the beginning of the objectid map (i = 0) and go to
 109        the end of it (i = disk_sb->s_oid_cursize).  Linear search is
 110        what we use, though it is possible that binary search would be
 111        more efficient after performing lots of deletions (which is
 112        when oids is large.)  We only check even i's. */
 113     while (i < sb_oid_cursize(rs)) {
 114         if (objectid_to_release == le32_to_cpu (map[i])) {
 115             /* This incrementation unallocates the objectid. */
 116             //map[i]++;
 117             map[i] = cpu_to_le32 (le32_to_cpu (map[i]) + 1);
 118
 119             /* Did we unallocate the last member of an odd sequence, and can shrink oids? */
 120             if (map[i] == map[i+1]) {
 121                 /* shrink objectid map */
 122                 memmove (map + i, map + i + 2,
 123                          (sb_oid_cursize(rs) - i - 2) * sizeof (__u32));
 124                 //disk_sb->s_oid_cursize -= 2;
 125                 set_sb_oid_cursize( rs, sb_oid_cursize(rs) - 2 );
 126
 127                 RFALSE( sb_oid_cursize(rs) < 2 ||
 128                         sb_oid_cursize(rs) > sb_oid_maxsize(rs),
 129                         "vs-15005: objectid map corrupted cur_size == %d (max == %d)",
 130                         sb_oid_cursize(rs), sb_oid_maxsize(rs));
 131             }
 132             return;
 133         }
 134
 135         if (objectid_to_release > le32_to_cpu (map[i]) &&
 136             objectid_to_release < le32_to_cpu (map[i + 1])) {
 137             /* size of objectid map is not changed */
 138             if (objectid_to_release + 1 == le32_to_cpu (map[i + 1])) {
 139                 //objectid_map[i+1]--;
 140                 map[i + 1] = cpu_to_le32 (le32_to_cpu (map[i + 1]) - 1);
 141                 return;
 142             }
 143
 144             /* JDM comparing two little-endian values for equality -- safe */
 145         if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
 146                 /* objectid map must be expanded, but there is no space */
 147                 PROC_INFO_INC( s, leaked_oid );
 148                 return;
 149         }
 150
 151             /* expand the objectid map*/
 152             memmove (map + i + 3, map + i + 1,
 153                      (sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
 154             map[i + 1] = cpu_to_le32 (objectid_to_release);
 155             map[i + 2] = cpu_to_le32 (objectid_to_release + 1);
 156             set_sb_oid_cursize( rs, sb_oid_cursize(rs) + 2 );
 157             return;
 158         }
 159         i += 2;
 160     }
 161
 162     reiserfs_warning (s, "vs-15011: reiserfs_release_objectid: tried to free free object id (%lu)",
 163                       ( long unsigned ) objectid_to_release);
 164 }
 165
 166
 167 int reiserfs_convert_objectid_map_v1(struct super_block *s) {
 168     struct reiserfs_super_block *disk_sb = SB_DISK_SUPER_BLOCK (s);
 169     int cur_size = sb_oid_cursize(disk_sb);
 170     int new_size = (s->s_blocksize - SB_SIZE) / sizeof(__u32) / 2 * 2 ;
 171     int old_max = sb_oid_maxsize(disk_sb);
 172     struct reiserfs_super_block_v1 *disk_sb_v1 ;
 173     __u32 *objectid_map, *new_objectid_map ;
 174     int i ;
 175
 176     disk_sb_v1=(struct reiserfs_super_block_v1 *)(SB_BUFFER_WITH_SB(s)->b_data);
 177     objectid_map = (__u32 *)(disk_sb_v1 + 1) ;
 178     new_objectid_map = (__u32 *)(disk_sb + 1) ;
 179
 180     if (cur_size > new_size) {
 181         /* mark everyone used that was listed as free at the end of the objectid
 182         ** map
 183         */
 184         objectid_map[new_size - 1] = objectid_map[cur_size - 1] ;
 185         set_sb_oid_cursize(disk_sb,new_size) ;
 186     }
 187     /* move the smaller objectid map past the end of the new super */
 188     for (i = new_size - 1 ; i >= 0 ; i--) {
 189         objectid_map[i + (old_max - new_size)] = objectid_map[i] ;
 190     }
 191
 192
 193     /* set the max size so we don't overflow later */
 194     set_sb_oid_maxsize(disk_sb,new_size) ;
 195
 196     /* Zero out label and generate random UUID */
 197     memset(disk_sb->s_label, 0, sizeof(disk_sb->s_label)) ;
 198     generate_random_uuid(disk_sb->s_uuid);
 199
 200     /* finally, zero out the unused chunk of the new super */
 201     memset(disk_sb->s_unused, 0, sizeof(disk_sb->s_unused)) ;
 202     return 0 ;
 203 }
 204