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 8d1154eb460efe588eaed3d439c1caaca149fa362Theodore Ts'o#include "config.h" 98fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o#include "e2fsck.h" 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) { 42e9a5c6e3607d17641543aa5e801af22563fb1410Theodore Ts'o fprintf(stderr, "Couldn't reallocate dx_dir_info " 43e9a5c6e3607d17641543aa5e801af22563fb1410Theodore Ts'o "structure to %d entries\n", 44e9a5c6e3607d17641543aa5e801af22563fb1410Theodore Ts'o ctx->dx_dir_info_size); 45e9a5c6e3607d17641543aa5e801af22563fb1410Theodore Ts'o fatal_error(ctx, 0); 468fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size -= 10; 478fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return; 488fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 498fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 508fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 518fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o /* 528fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Normally, add_dx_dir_info is called with each inode in 538fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * sequential order; but once in a while (like when pass 3 548fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * needs to recreate the root directory or lost+found 558fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * directory) it is called out of order. In those cases, we 568fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * need to move the dx_dir_info entries down to make room, since 578fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * the dx_dir_info array needs to be sorted by inode number for 588fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * get_dx_dir_info()'s sake. 598fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 608fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info_count && 618fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) { 628fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o for (i = ctx->dx_dir_info_count-1; i > 0; i--) 638fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info[i-1].ino < ino) 648fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o break; 658fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = &ctx->dx_dir_info[i]; 66efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o if (dir->ino != ino) 678fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o for (j = ctx->dx_dir_info_count++; j > i; j--) 688fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1]; 698fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } else 708fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++]; 71efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 728fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->ino = ino; 738fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->numblocks = num_blocks; 748fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->hashversion = 0; 758fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks 768fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * sizeof (struct dx_dirblock_info), 778fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o "dx_block info array"); 788fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 798fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 808fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 818fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 828fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * get_dx_dir_info() --- given an inode number, try to find the directory 838fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * information entry for it. 848fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 858fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ostruct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino) 868fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 878fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o int low, high, mid; 888fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 898fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o low = 0; 908fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o high = ctx->dx_dir_info_count-1; 918fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (!ctx->dx_dir_info) 928fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 938fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[low].ino) 948fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[low]; 958fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[high].ino) 968fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[high]; 978fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 988fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o while (low < high) { 998fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o mid = (low+high)/2; 1008fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (mid == low || mid == high) 1018fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o break; 1028fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino == ctx->dx_dir_info[mid].ino) 1038fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return &ctx->dx_dir_info[mid]; 1048fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ino < ctx->dx_dir_info[mid].ino) 1058fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o high = mid; 1068fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o else 1078fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o low = mid; 1088fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1098fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 1108fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1118fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1128fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1138fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Free the dx_dir_info structure when it isn't needed any more. 1148fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1158fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ovoid e2fsck_free_dx_dir_info(e2fsck_t ctx) 1168fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1178fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o int i; 1188fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o struct dx_dir_info *dir; 119efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 1208fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (ctx->dx_dir_info) { 1218fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir = ctx->dx_dir_info; 12223f75f6efaac6b756e0f3e4e1d33b6798347f66aTheodore Ts'o for (i=0; i < ctx->dx_dir_info_count; i++,dir++) { 1238fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (dir->dx_block) { 124c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&dir->dx_block); 1258fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o dir->dx_block = 0; 1268fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1278fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 128c4e3d3f374b409500e3dd05c0b0eca6ac98a6b4eTheodore Ts'o ext2fs_free_mem(&ctx->dx_dir_info); 1298fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info = 0; 1308fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o } 1318fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_size = 0; 1328fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o ctx->dx_dir_info_count = 0; 1338fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1348fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1358fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1368fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * Return the count of number of directories in the dx_dir_info structure 1378fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1388fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'oint e2fsck_get_num_dx_dirinfo(e2fsck_t ctx) 1398fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1408fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return ctx->dx_dir_info_count; 1418fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 1428fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1438fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o/* 1448fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o * A simple interator function 1458fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o */ 1468fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'ostruct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control) 1478fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o{ 1488fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o if (*control >= ctx->dx_dir_info_count) 1498fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return 0; 1508fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 1518fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o return(ctx->dx_dir_info + (*control)++); 1528fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o} 153