264 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright (C) 2011 Red Hat, Inc.4 *5 * This file is released under the GPL.6 */7 8#include "dm-btree-internal.h"9#include "dm-transaction-manager.h"10 11#include <linux/device-mapper.h>12 13#define DM_MSG_PREFIX "btree spine"14 15/*----------------------------------------------------------------*/16 17#define BTREE_CSUM_XOR 12110718 19static void node_prepare_for_write(const struct dm_block_validator *v,20 struct dm_block *b,21 size_t block_size)22{23 struct btree_node *n = dm_block_data(b);24 struct node_header *h = &n->header;25 26 h->blocknr = cpu_to_le64(dm_block_location(b));27 h->csum = cpu_to_le32(dm_bm_checksum(&h->flags,28 block_size - sizeof(__le32),29 BTREE_CSUM_XOR));30}31 32static int node_check(const struct dm_block_validator *v,33 struct dm_block *b,34 size_t block_size)35{36 struct btree_node *n = dm_block_data(b);37 struct node_header *h = &n->header;38 size_t value_size;39 __le32 csum_disk;40 uint32_t flags, nr_entries, max_entries;41 42 if (dm_block_location(b) != le64_to_cpu(h->blocknr)) {43 DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__,44 le64_to_cpu(h->blocknr), dm_block_location(b));45 return -ENOTBLK;46 }47 48 csum_disk = cpu_to_le32(dm_bm_checksum(&h->flags,49 block_size - sizeof(__le32),50 BTREE_CSUM_XOR));51 if (csum_disk != h->csum) {52 DMERR_LIMIT("%s failed: csum %u != wanted %u", __func__,53 le32_to_cpu(csum_disk), le32_to_cpu(h->csum));54 return -EILSEQ;55 }56 57 nr_entries = le32_to_cpu(h->nr_entries);58 max_entries = le32_to_cpu(h->max_entries);59 value_size = le32_to_cpu(h->value_size);60 61 if (sizeof(struct node_header) +62 (sizeof(__le64) + value_size) * max_entries > block_size) {63 DMERR_LIMIT("%s failed: max_entries too large", __func__);64 return -EILSEQ;65 }66 67 if (nr_entries > max_entries) {68 DMERR_LIMIT("%s failed: too many entries", __func__);69 return -EILSEQ;70 }71 72 /*73 * The node must be either INTERNAL or LEAF.74 */75 flags = le32_to_cpu(h->flags);76 if (!(flags & INTERNAL_NODE) && !(flags & LEAF_NODE)) {77 DMERR_LIMIT("%s failed: node is neither INTERNAL or LEAF", __func__);78 return -EILSEQ;79 }80 81 return 0;82}83 84const struct dm_block_validator btree_node_validator = {85 .name = "btree_node",86 .prepare_for_write = node_prepare_for_write,87 .check = node_check88};89 90/*----------------------------------------------------------------*/91 92int bn_read_lock(struct dm_btree_info *info, dm_block_t b,93 struct dm_block **result)94{95 return dm_tm_read_lock(info->tm, b, &btree_node_validator, result);96}97 98static int bn_shadow(struct dm_btree_info *info, dm_block_t orig,99 struct dm_btree_value_type *vt,100 struct dm_block **result)101{102 int r, inc;103 104 r = dm_tm_shadow_block(info->tm, orig, &btree_node_validator,105 result, &inc);106 if (!r && inc)107 inc_children(info->tm, dm_block_data(*result), vt);108 109 return r;110}111 112int new_block(struct dm_btree_info *info, struct dm_block **result)113{114 return dm_tm_new_block(info->tm, &btree_node_validator, result);115}116 117void unlock_block(struct dm_btree_info *info, struct dm_block *b)118{119 dm_tm_unlock(info->tm, b);120}121 122/*----------------------------------------------------------------*/123 124void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info)125{126 s->info = info;127 s->count = 0;128 s->nodes[0] = NULL;129 s->nodes[1] = NULL;130}131 132void exit_ro_spine(struct ro_spine *s)133{134 int i;135 136 for (i = 0; i < s->count; i++)137 unlock_block(s->info, s->nodes[i]);138}139 140int ro_step(struct ro_spine *s, dm_block_t new_child)141{142 int r;143 144 if (s->count == 2) {145 unlock_block(s->info, s->nodes[0]);146 s->nodes[0] = s->nodes[1];147 s->count--;148 }149 150 r = bn_read_lock(s->info, new_child, s->nodes + s->count);151 if (!r)152 s->count++;153 154 return r;155}156 157void ro_pop(struct ro_spine *s)158{159 BUG_ON(!s->count);160 --s->count;161 unlock_block(s->info, s->nodes[s->count]);162}163 164struct btree_node *ro_node(struct ro_spine *s)165{166 struct dm_block *block;167 168 BUG_ON(!s->count);169 block = s->nodes[s->count - 1];170 171 return dm_block_data(block);172}173 174/*----------------------------------------------------------------*/175 176void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info)177{178 s->info = info;179 s->count = 0;180}181 182void exit_shadow_spine(struct shadow_spine *s)183{184 int i;185 186 for (i = 0; i < s->count; i++)187 unlock_block(s->info, s->nodes[i]);188}189 190int shadow_step(struct shadow_spine *s, dm_block_t b,191 struct dm_btree_value_type *vt)192{193 int r;194 195 if (s->count == 2) {196 unlock_block(s->info, s->nodes[0]);197 s->nodes[0] = s->nodes[1];198 s->count--;199 }200 201 r = bn_shadow(s->info, b, vt, s->nodes + s->count);202 if (!r) {203 if (!s->count)204 s->root = dm_block_location(s->nodes[0]);205 206 s->count++;207 }208 209 return r;210}211 212struct dm_block *shadow_current(struct shadow_spine *s)213{214 BUG_ON(!s->count);215 216 return s->nodes[s->count - 1];217}218 219struct dm_block *shadow_parent(struct shadow_spine *s)220{221 BUG_ON(s->count != 2);222 223 return s->count == 2 ? s->nodes[0] : NULL;224}225 226int shadow_has_parent(struct shadow_spine *s)227{228 return s->count >= 2;229}230 231dm_block_t shadow_root(struct shadow_spine *s)232{233 return s->root;234}235 236static void le64_inc(void *context, const void *value_le, unsigned int count)237{238 dm_tm_with_runs(context, value_le, count, dm_tm_inc_range);239}240 241static void le64_dec(void *context, const void *value_le, unsigned int count)242{243 dm_tm_with_runs(context, value_le, count, dm_tm_dec_range);244}245 246static int le64_equal(void *context, const void *value1_le, const void *value2_le)247{248 __le64 v1_le, v2_le;249 250 memcpy(&v1_le, value1_le, sizeof(v1_le));251 memcpy(&v2_le, value2_le, sizeof(v2_le));252 return v1_le == v2_le;253}254 255void init_le64_type(struct dm_transaction_manager *tm,256 struct dm_btree_value_type *vt)257{258 vt->context = tm;259 vt->size = sizeof(__le64);260 vt->inc = le64_inc;261 vt->dec = le64_dec;262 vt->equal = le64_equal;263}264