1342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o/* 2342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * ea_refcount.c 3efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * 4342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * Copyright (C) 2001 Theodore Ts'o. This file may be 5342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * redistributed under the terms of the GNU Public License. 6342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 7342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 8342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#if HAVE_UNISTD_H 9342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#include <unistd.h> 10342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#endif 11342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#include <string.h> 12342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#include <stdio.h> 13342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 140eeec8ac61bf1eaa31533b2be825cd75580829c9Theodore Ts'o#ifdef TEST_PROGRAM 150eeec8ac61bf1eaa31533b2be825cd75580829c9Theodore Ts'o#undef ENABLE_NLS 160eeec8ac61bf1eaa31533b2be825cd75580829c9Theodore Ts'o#endif 17342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#include "e2fsck.h" 18342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 19342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o/* 20342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * The strategy we use for keeping track of EA refcounts is as 21342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * follows. We keep a sorted array of first EA blocks and its 22342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * reference counts. Once the refcount has dropped to zero, it is 23342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * removed from the array to save memory space. Once the EA block is 24efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * checked, its bit is set in the block_ea_map bitmap. 25342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 26342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ostruct ea_refcount_el { 27e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall blk64_t ea_blk; 28342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int ea_count; 29342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o}; 30342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 31342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ostruct ea_refcount { 32342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk_t count; 33342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk_t size; 34544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o blk_t cursor; 35342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *list; 36342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o}; 37342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 38342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ovoid ea_refcount_free(ext2_refcount_t refcount) 39342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 40342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!refcount) 41342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return; 42342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 43342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->list) 44c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&refcount->list); 45c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&refcount); 46342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 47342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 48342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oerrcode_t ea_refcount_create(int size, ext2_refcount_t *ret) 49342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 50342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ext2_refcount_t refcount; 51342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o errcode_t retval; 52342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o size_t bytes; 53342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 54c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount); 55342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 56342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return retval; 57342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o memset(refcount, 0, sizeof(struct ea_refcount)); 58342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 59342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!size) 60342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o size = 500; 61342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->size = size; 62342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o bytes = (size_t) (size * sizeof(struct ea_refcount_el)); 63342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#ifdef DEBUG 64342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Refcount allocated %d entries, %d bytes.\n", 65342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->size, bytes); 66342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#endif 67c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o retval = ext2fs_get_mem(bytes, &refcount->list); 68342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 69342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o goto errout; 70342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o memset(refcount->list, 0, bytes); 71342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 72342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->count = 0; 73342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->cursor = 0; 74342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 75342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = refcount; 76342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 77342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 78342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oerrout: 79342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ea_refcount_free(refcount); 80342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return(retval); 81342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 82342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 83342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o/* 84342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * collapse_refcount() --- go through the refcount array, and get rid 85342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * of any count == zero entries 86342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 87342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ostatic void refcount_collapse(ext2_refcount_t refcount) 88342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 89544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o unsigned int i, j; 90342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *list; 91342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 92342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o list = refcount->list; 93342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o for (i = 0, j = 0; i < refcount->count; i++) { 94342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (list[i].ea_count) { 95342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (i != j) 96342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o list[j] = list[i]; 97342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o j++; 98342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 99342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 100342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#if defined(DEBUG) || defined(TEST_PROGRAM) 101342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Refcount_collapse: size was %d, now %d\n", 102342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->count, j); 103342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#endif 104342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->count = j; 105342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 106342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 107342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 108342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o/* 109342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * insert_refcount_el() --- Insert a new entry into the sorted list at a 110342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * specified position. 111342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 112342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ostatic struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount, 113e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall blk64_t blk, int pos) 114342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 115342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *el; 116342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o errcode_t retval; 117342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk_t new_size = 0; 118342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int num; 119342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 120342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count >= refcount->size) { 121342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o new_size = refcount->size + 100; 122342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#ifdef DEBUG 123342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Reallocating refcount %d entries...\n", new_size); 124efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o#endif 125342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o retval = ext2fs_resize_mem((size_t) refcount->size * 126342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o sizeof(struct ea_refcount_el), 127342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o (size_t) new_size * 128342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o sizeof(struct ea_refcount_el), 129c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o &refcount->list); 130342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 131342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 132342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->size = new_size; 133342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 134342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o num = (int) refcount->count - pos; 135342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (num < 0) 136342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; /* should never happen */ 137342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (num) { 138342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o memmove(&refcount->list[pos+1], &refcount->list[pos], 139342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o sizeof(struct ea_refcount_el) * num); 140342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 141342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->count++; 142342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el = &refcount->list[pos]; 143342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el->ea_count = 0; 144342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el->ea_blk = blk; 145342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return el; 146342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 147342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 148342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 149342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o/* 150342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * get_refcount_el() --- given an block number, try to find refcount 151342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * information in the sorted list. If the create flag is set, 152342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * and we can't find an entry, create one in the sorted list. 153342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 154342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ostatic struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount, 155e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall blk64_t blk, int create) 156342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 157342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int low, high, mid; 158342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 159342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!refcount || !refcount->list) 160342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 161342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oretry: 162342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o low = 0; 163342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o high = (int) refcount->count-1; 164342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (create && ((refcount->count == 0) || 165342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o (blk > refcount->list[high].ea_blk))) { 166342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count >= refcount->size) 167342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount_collapse(refcount); 168342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 169342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return insert_refcount_el(refcount, blk, 170342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o (unsigned) refcount->count); 171342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 172342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count == 0) 173342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 174efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 175342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->cursor >= refcount->count) 176342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->cursor = 0; 177342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (blk == refcount->list[refcount->cursor].ea_blk) 178342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return &refcount->list[refcount->cursor++]; 179342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#ifdef DEBUG 180342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Non-cursor get_refcount_el: %u\n", blk); 181342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#endif 182342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o while (low <= high) { 183342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o mid = (low+high)/2; 184342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (blk == refcount->list[mid].ea_blk) { 185342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->cursor = mid+1; 186342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return &refcount->list[mid]; 187342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 188342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (blk < refcount->list[mid].ea_blk) 189342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o high = mid-1; 190342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o else 191342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o low = mid+1; 192342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 193342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o /* 194342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * If we need to create a new entry, it should be right at 195342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * low (where high will be left at low-1). 196342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 197342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (create) { 198342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count >= refcount->size) { 199342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount_collapse(refcount); 200342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count < refcount->size) 201342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o goto retry; 202342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 203342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return insert_refcount_el(refcount, blk, low); 204342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 205342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 206342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 207342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 208e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallerrcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk64_t blk, 209342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int *ret) 210342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 211342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *el; 212efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 213342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el = get_refcount_el(refcount, blk, 0); 214342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!el) { 215342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = 0; 216342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 217342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 218342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = el->ea_count; 219342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 220342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 221342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 222e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallerrcode_t ea_refcount_increment(ext2_refcount_t refcount, blk64_t blk, int *ret) 223342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 224342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *el; 225342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 226342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el = get_refcount_el(refcount, blk, 1); 227342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!el) 228342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return EXT2_ET_NO_MEMORY; 229342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el->ea_count++; 230342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 231342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (ret) 232342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = el->ea_count; 233342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 234342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 235342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 236e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallerrcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk64_t blk, int *ret) 237342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 238342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *el; 239342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 240342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el = get_refcount_el(refcount, blk, 0); 241342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!el || el->ea_count == 0) 242342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 243342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 244342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el->ea_count--; 245342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 246342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (ret) 247342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = el->ea_count; 248342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 249342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 250342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 251e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallerrcode_t ea_refcount_store(ext2_refcount_t refcount, blk64_t blk, int count) 252342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 253342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *el; 254342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 255342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o /* 256342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o * Get the refcount element 257342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o */ 258342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el = get_refcount_el(refcount, blk, count ? 1 : 0); 259342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!el) 260342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return count ? EXT2_ET_NO_MEMORY : 0; 261342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o el->ea_count = count; 262342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 263342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 264342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 265342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oblk_t ext2fs_get_refcount_size(ext2_refcount_t refcount) 266342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 267342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!refcount) 268342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 269342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 270342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return refcount->size; 271342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 272342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 273342d847db355d81299218e07a1e58ece82080a04Theodore Ts'ovoid ea_refcount_intr_begin(ext2_refcount_t refcount) 274342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 275342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->cursor = 0; 276342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 277342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 278342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 279e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallblk64_t ea_refcount_intr_next(ext2_refcount_t refcount, 280342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int *ret) 281342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 282342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o struct ea_refcount_el *list; 283efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 284342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o while (1) { 285342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->cursor >= refcount->count) 286342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return 0; 287342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o list = refcount->list; 288342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (list[refcount->cursor].ea_count) { 289342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (ret) 290342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o *ret = list[refcount->cursor].ea_count; 291342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return list[refcount->cursor++].ea_blk; 292342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 293342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount->cursor++; 294342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 295342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 296342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 297342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 298342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#ifdef TEST_PROGRAM 299342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 300342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oerrcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out) 301342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 302342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o errcode_t ret = 0; 303342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int i; 304342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o const char *bad = "bad refcount"; 305efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 306342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->count > refcount->size) { 307342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o fprintf(out, "%s: count > size\n", bad); 308342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 309342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 310342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o for (i=1; i < refcount->count; i++) { 311342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) { 312e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall fprintf(out, 313e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "%s: list[%d].blk=%llu, list[%d].blk=%llu\n", 314342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o bad, i-1, refcount->list[i-1].ea_blk, 315342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o i, refcount->list[i].ea_blk); 316342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ret = EXT2_ET_INVALID_ARGUMENT; 317342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 318342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 319342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o return ret; 320342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 321342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 322342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_END 0 323342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_CREATE 1 324342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_FREE 2 325342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_STORE 3 326342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_INCR 4 327342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_DECR 5 328342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_FETCH 6 329342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_VALIDATE 7 330342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_LIST 8 331342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#define BCODE_COLLAPSE 9 332342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 333342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oint bcode_program[] = { 334342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_CREATE, 5, 335342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 3, 3, 336342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 4, 4, 337342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 1, 1, 338342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 8, 8, 339342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 2, 2, 340342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 4, 0, 341342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 2, 0, 342342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 6, 6, 343342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_VALIDATE, 344342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 4, 4, 345342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 2, 2, 346342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_FETCH, 1, 347342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_FETCH, 2, 348342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_INCR, 3, 349342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_INCR, 3, 350342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_DECR, 4, 351342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 4, 4, 352342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_VALIDATE, 353342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 20, 20, 354342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 40, 40, 355342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 30, 30, 356342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_STORE, 10, 10, 357342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_DECR, 30, 358342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_FETCH, 30, 359342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_DECR, 2, 360342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_DECR, 2, 361342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_COLLAPSE, 362342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_LIST, 363342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_VALIDATE, 364342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_FREE, 365342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o BCODE_END 366342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o}; 367342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 368342d847db355d81299218e07a1e58ece82080a04Theodore Ts'oint main(int argc, char **argv) 369342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o{ 370342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int i = 0; 371342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ext2_refcount_t refcount; 372342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o int size, arg; 373e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall blk64_t blk; 374342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o errcode_t retval; 375342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 376342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o while (1) { 377342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o switch (bcode_program[i++]) { 378342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_END: 379342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o exit(0); 380342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_CREATE: 381342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o size = bcode_program[i++]; 382342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o retval = ea_refcount_create(size, &refcount); 383342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) { 384e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall com_err("ea_refcount_create", retval, 385e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while creating size %d", size); 386342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o exit(1); 387342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } else 388342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Creating refcount with size %d\n", 389342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o size); 390342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 391342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_FREE: 392342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ea_refcount_free(refcount); 393342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount = 0; 394342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Freeing refcount\n"); 395342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 396342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_STORE: 397342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk = (blk_t) bcode_program[i++]; 398342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o arg = bcode_program[i++]; 399e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall printf("Storing blk %llu with value %d\n", blk, arg); 4006b56f3d92d08806ab415e8fd883480f7f9c148e8Andreas Dilger retval = ea_refcount_store(refcount, blk, arg); 401342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 402e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall com_err("ea_refcount_store", retval, 403e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while storing blk %llu", blk); 404342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 405342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_FETCH: 406342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk = (blk_t) bcode_program[i++]; 407342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o retval = ea_refcount_fetch(refcount, blk, &arg); 408342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 409e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall com_err("ea_refcount_fetch", retval, 410e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while fetching blk %llu", blk); 411342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o else 412e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall printf("bcode_fetch(%llu) returns %d\n", 413342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk, arg); 414342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 415342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_INCR: 416342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk = (blk_t) bcode_program[i++]; 417e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall retval = ea_refcount_increment(refcount, blk, &arg); 418342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 419342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o com_err("ea_refcount_increment", retval, 420e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while incrementing blk %llu", blk); 421342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o else 422e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall printf("bcode_increment(%llu) returns %d\n", 423342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk, arg); 424342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 425342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_DECR: 426342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk = (blk_t) bcode_program[i++]; 427e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall retval = ea_refcount_decrement(refcount, blk, &arg); 428342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 429342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o com_err("ea_refcount_decrement", retval, 430e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while decrementing blk %llu", blk); 431342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o else 432e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall printf("bcode_decrement(%llu) returns %d\n", 433342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o blk, arg); 434342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 435342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_VALIDATE: 436342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o retval = ea_refcount_validate(refcount, stderr); 437342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (retval) 438e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall com_err("ea_refcount_validate", retval, 439e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall "while validating"); 440342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o else 441342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o printf("Refcount validation OK.\n"); 442342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 443342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_LIST: 444342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o ea_refcount_intr_begin(refcount); 445342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o while (1) { 446e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall blk = ea_refcount_intr_next(refcount, &arg); 447342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o if (!blk) 448342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 449e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall printf("\tblk=%llu, count=%d\n", blk, arg); 450342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 451342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 452342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o case BCODE_COLLAPSE: 453342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o refcount_collapse(refcount); 454342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o break; 455342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 456efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 457342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o } 458342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o} 459342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o 460342d847db355d81299218e07a1e58ece82080a04Theodore Ts'o#endif 461