18fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 28fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * dirinfo.c --- maintains the directory information table for e2fsck. 38fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * 48fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Copyright (C) 1993 Theodore Ts'o. This file may be redistributed 58fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * under the terms of the GNU Public License. 68fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 78fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 88fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#include "e2fsck.h" 98fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#ifdef ENABLE_HTREE 108fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 118fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 128fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * This subroutine is called during pass1 to create a directory info 138fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * entry. During pass1, the passed-in parent is 0; it will get filled 14efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * in during pass2. 158fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 168fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ovoid e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks) 178fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 188fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o struct dx_dir_info *dir; 198fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o int i, j; 208fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o errcode_t retval; 218fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o unsigned long old_size; 228fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 238fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#if 0 248fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o printf("add_dx_dir_info for inode %lu...\n", ino); 258fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#endif 268fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (!ctx->dx_dir_info) { 278fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_count = 0; 288fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size = 100; /* Guess */ 298fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info = (struct dx_dir_info *) 308fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size 318fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * sizeof (struct dx_dir_info), 328fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o "directory map"); 338fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 34efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 358fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) { 368fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info); 378fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size += 10; 388fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size * 398fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o sizeof(struct dx_dir_info), 40c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o &ctx->dx_dir_info); 418fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (retval) { 428fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size -= 10; 438fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return; 448fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 458fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 468fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 478fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o /* 488fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Normally, add_dx_dir_info is called with each inode in 498fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * sequential order; but once in a while (like when pass 3 508fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * needs to recreate the root directory or lost+found 518fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * directory) it is called out of order. In those cases, we 528fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * need to move the dx_dir_info entries down to make room, since 538fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * the dx_dir_info array needs to be sorted by inode number for 548fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * get_dx_dir_info()'s sake. 558fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 568fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info_count && 578fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) { 588fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o for (i = ctx->dx_dir_info_count-1; i > 0; i--) 598fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info[i-1].ino < ino) 608fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o break; 618fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = &ctx->dx_dir_info[i]; 62efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o if (dir->ino != ino) 638fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o for (j = ctx->dx_dir_info_count++; j > i; j--) 648fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1]; 658fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } else 668fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++]; 67efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 688fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->ino = ino; 698fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->numblocks = num_blocks; 708fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->hashversion = 0; 718fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks 728fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * sizeof (struct dx_dirblock_info), 738fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o "dx_block info array"); 748fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 758fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 768fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 778fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 788fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * get_dx_dir_info() --- given an inode number, try to find the directory 798fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * information entry for it. 808fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 818fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ostruct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino) 828fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 838fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o int low, high, mid; 848fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 858fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o low = 0; 868fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o high = ctx->dx_dir_info_count-1; 878fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (!ctx->dx_dir_info) 888fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 898fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[low].ino) 908fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[low]; 918fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[high].ino) 928fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[high]; 938fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 948fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o while (low < high) { 958fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o mid = (low+high)/2; 968fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (mid == low || mid == high) 978fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o break; 988fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[mid].ino) 998fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[mid]; 1008fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino < ctx->dx_dir_info[mid].ino) 1018fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o high = mid; 1028fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o else 1038fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o low = mid; 1048fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1058fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 1068fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1078fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1088fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1098fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Free the dx_dir_info structure when it isn't needed any more. 1108fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1118fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ovoid e2fsck_free_dx_dir_info(e2fsck_t ctx) 1128fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1138fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o int i; 1148fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o struct dx_dir_info *dir; 115efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 1168fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info) { 1178fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = ctx->dx_dir_info; 11823f75f6efaac6b756e0f3e4e1d33b6798347f66aTheodore Ts'o for (i=0; i < ctx->dx_dir_info_count; i++,dir++) { 1198fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (dir->dx_block) { 120c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&dir->dx_block); 1218fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->dx_block = 0; 1228fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1238fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 124c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&ctx->dx_dir_info); 1258fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info = 0; 1268fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1278fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size = 0; 1288fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_count = 0; 1298fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1308fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1318fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1328fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Return the count of number of directories in the dx_dir_info structure 1338fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1348fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'oint e2fsck_get_num_dx_dirinfo(e2fsck_t ctx) 1358fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1368fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return ctx->dx_dir_info_count; 1378fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1388fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1398fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1408fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * A simple interator function 1418fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1428fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ostruct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control) 1438fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1448fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (*control >= ctx->dx_dir_info_count) 1458fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 1468fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1478fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return(ctx->dx_dir_info + (*control)++); 1488fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1498fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1508fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#endif /* ENABLE_HTREE */ 151