119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * dirinfo.c --- maintains the directory information table for e2fsck. 319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Copyright (C) 1993 Theodore Ts'o. This file may be redistributed 519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * under the terms of the GNU Public License. 619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "e2fsck.h" 919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#ifdef ENABLE_HTREE 1019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 1219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * This subroutine is called during pass1 to create a directory info 1319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * entry. During pass1, the passed-in parent is 0; it will get filled 143984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt * in during pass2. 1519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 1619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectvoid e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks) 1719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 1819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct dx_dir_info *dir; 1919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project int i, j; 2019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project errcode_t retval; 2119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project unsigned long old_size; 2219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#if 0 2419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project printf("add_dx_dir_info for inode %lu...\n", ino); 2519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif 2619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (!ctx->dx_dir_info) { 2719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_count = 0; 2819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_size = 100; /* Guess */ 2919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info = (struct dx_dir_info *) 3019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size 3119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * sizeof (struct dx_dir_info), 3219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project "directory map"); 3319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 343984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt 3519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) { 3619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info); 3719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_size += 10; 3819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size * 3919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project sizeof(struct dx_dir_info), 4019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project &ctx->dx_dir_info); 4119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (retval) { 4219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_size -= 10; 4319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return; 4419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 4519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 4619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /* 4819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Normally, add_dx_dir_info is called with each inode in 4919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * sequential order; but once in a while (like when pass 3 5019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * needs to recreate the root directory or lost+found 5119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * directory) it is called out of order. In those cases, we 5219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * need to move the dx_dir_info entries down to make room, since 5319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * the dx_dir_info array needs to be sorted by inode number for 5419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * get_dx_dir_info()'s sake. 5519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 5619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ctx->dx_dir_info_count && 5719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) { 5819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project for (i = ctx->dx_dir_info_count-1; i > 0; i--) 5919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ctx->dx_dir_info[i-1].ino < ino) 6019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project break; 6119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir = &ctx->dx_dir_info[i]; 623984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt if (dir->ino != ino) 6319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project for (j = ctx->dx_dir_info_count++; j > i; j--) 6419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1]; 6519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } else 6619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++]; 673984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt 6819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir->ino = ino; 6919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir->numblocks = num_blocks; 7019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir->hashversion = 0; 7119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks 7219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * sizeof (struct dx_dirblock_info), 7319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project "dx_block info array"); 7419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 7619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 7819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * get_dx_dir_info() --- given an inode number, try to find the directory 7919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * information entry for it. 8019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 8119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstruct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino) 8219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 8319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project int low, high, mid; 8419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 8519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project low = 0; 8619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project high = ctx->dx_dir_info_count-1; 8719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (!ctx->dx_dir_info) 8819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return 0; 8919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ino == ctx->dx_dir_info[low].ino) 9019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return &ctx->dx_dir_info[low]; 9119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ino == ctx->dx_dir_info[high].ino) 9219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return &ctx->dx_dir_info[high]; 9319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 9419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project while (low < high) { 9519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project mid = (low+high)/2; 9619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (mid == low || mid == high) 9719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project break; 9819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ino == ctx->dx_dir_info[mid].ino) 9919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return &ctx->dx_dir_info[mid]; 10019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ino < ctx->dx_dir_info[mid].ino) 10119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project high = mid; 10219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project else 10319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project low = mid; 10419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 10519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return 0; 10619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 10719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 10919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Free the dx_dir_info structure when it isn't needed any more. 11019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 11119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectvoid e2fsck_free_dx_dir_info(e2fsck_t ctx) 11219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 11319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project int i; 11419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct dx_dir_info *dir; 1153984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt 11619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (ctx->dx_dir_info) { 11719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir = ctx->dx_dir_info; 1183984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt for (i=0; i < ctx->dx_dir_info_count; i++,dir++) { 11919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (dir->dx_block) { 12019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ext2fs_free_mem(&dir->dx_block); 12119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project dir->dx_block = 0; 12219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 12319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 12419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ext2fs_free_mem(&ctx->dx_dir_info); 12519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info = 0; 12619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 12719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_size = 0; 12819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ctx->dx_dir_info_count = 0; 12919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 13019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 13119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 13219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Return the count of number of directories in the dx_dir_info structure 13319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 13419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectint e2fsck_get_num_dx_dirinfo(e2fsck_t ctx) 13519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 13619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return ctx->dx_dir_info_count; 13719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 13819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 13919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 14019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * A simple interator function 14119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 14219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstruct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control) 14319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 14419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (*control >= ctx->dx_dir_info_count) 14519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return 0; 14619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 14719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return(ctx->dx_dir_info + (*control)++); 14819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 14919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 15019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif /* ENABLE_HTREE */ 151