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