From f466f41955f3050d47cfd687680f2f356e501a7a Mon Sep 17 00:00:00 2001 From: Vitaliy Kuznetsov Date: Tue, 11 Jun 2024 13:40:38 +0200 Subject: [PATCH] EX-9609 lipe: Add sorting to reports by directory sizes This patch does not change format the display of tables in directory reports. This patch adds sorting to the directory size report. This patch also sorts the TOP-X rating table. Sorting occurs in descending order of size. Sorting is done based on the allocated size. Test-Parameters: trivial testlist=sanity-lipe-scan3,sanity-lipe-find3 Signed-off-by: Vitaliy Kuznetsov Change-Id: I5d641660d7bf33cedb27612c04d1a7de43d78c75 Reviewed-on: https://review.whamcloud.com/c/ex/lustre-release/+/55395 Tested-by: jenkins Tested-by: Maloo Reviewed-by: Alexandre Ioffe Reviewed-by: Andreas Dilger --- lipe/src/lipe_scan3/ls3_dir_stats.c | 109 ++++++++++++++++++++++++++++++++++++ 1 file changed, 109 insertions(+) diff --git a/lipe/src/lipe_scan3/ls3_dir_stats.c b/lipe/src/lipe_scan3/ls3_dir_stats.c index e2e858e..6a3e562 100644 --- a/lipe/src/lipe_scan3/ls3_dir_stats.c +++ b/lipe/src/lipe_scan3/ls3_dir_stats.c @@ -179,6 +179,110 @@ static void ls3_stats_init_heap(struct ls3_stats_dir_general *d_stats) ls3_stats_create_heap(d_stats->lsdg_top_rating_limit); } +/** + * ls3_stats_get_max_alloc_size - finds the maximum allocated size in sectors + * from an array of directory objects. This function iterates through an array + * of pointers to `ls3_stats_dir_obj` structures and returns the maximum + * value of the `lsdo_alloc_size_in_sectors` field. + * + * @param lsdo_child Array of pointers to `ls3_stats_dir_obj` structures + * representing child directories. + * @param count_child_dirs The number of child directories in the array. + * @return The maximum allocated size in sectors among the child directories. + */ +static uint64_t ls3_stats_get_max_alloc_size( + struct ls3_stats_dir_obj **lsdo_child, uint32_t count_child_dirs) +{ + uint64_t max_size = lsdo_child[0]->lsdo_alloc_size_in_sectors; + uint32_t i; + + for (i = 1; i <= count_child_dirs; i++) { + if (lsdo_child[i]->lsdo_alloc_size_in_sectors > max_size) + max_size = lsdo_child[i]->lsdo_alloc_size_in_sectors; + } + + return max_size; +} + +/** + * ls3_stats_counting_sort - performs counting sort of lsdo_child[] according + * to the digit represented by exp. This function sorts an array of pointers + * to `ls3_stats_dir_obj` structures based on the value of the + * `lsdo_alloc_size_in_sectors` field, using counting sort algorithm. + * + * @param lsdo_child Array of pointers to `ls3_stats_dir_obj` structures + * representing child directories. + * @param count The number of elements in the lsdo_child[] array. + * @param exp The exponent representing the digit position to sort on. + */ +static void ls3_stats_counting_sort(struct ls3_stats_dir_obj **lsdo_child, + size_t count, uint64_t exp) +{ + struct ls3_stats_dir_obj **tmp = (struct ls3_stats_dir_obj**)xcalloc( + count + 1, + sizeof(struct ls3_stats_dir_obj*)); + int count_arr[10] = {0}; + int tmp_n; + int i; + + /* Store count of occurrences in count_arr[] */ + for (i = 0; i <= count; i++) { + tmp_n = (lsdo_child[i]->lsdo_alloc_size_in_sectors / exp) % 10; + count_arr[tmp_n]++; + } + + for (i = 8; i >= 0; i--) { + count_arr[i] += count_arr[i + 1]; + } + + /* Build the tmp array */ + for (i = count; i >= 0; i--) { + tmp_n = (lsdo_child[i]->lsdo_alloc_size_in_sectors / exp) % 10; + tmp[count_arr[tmp_n] - 1] = lsdo_child[i]; + count_arr[tmp_n]--; + } + + /* Copy the tmp array to lsdo_child[] */ + for (i = 0; i <= count; i++) { + lsdo_child[i] = tmp[i]; + } + + free(tmp); +} + +/** + * ls3_stats_radix_sort - performs radix sort on an array of directory objects + * based on allocated size in sectors. + * + * This function sorts an array of pointers to `ls3_stats_dir_obj` structures + * in descending order of the `lsdo_alloc_size_in_sectors` field using the + * radix sort algorithm. Radix Sort processes each digit of the numbers from + * the least significant digit to the most significant digit. + * + * The time complexity of this function is O(d * (n + b)), where: + * - d is the number of digits in the largest number (allocated size in sectors). + * - n is the number of elements in the array. + * - b is the base used for the digit extraction (10 for decimal digits). + * + * @param lsdo_child Array of pointers to `ls3_stats_dir_obj` structures + * representing child directories. + * @param count_child_dirs The number of child directories in the array. + */ +static void ls3_stats_radix_sort(struct ls3_stats_dir_obj **lsdo_child, + size_t count_child_dirs) +{ + uint64_t max_size; + uint64_t exponent; + + if (count_child_dirs < 1) + return; + + max_size = ls3_stats_get_max_alloc_size(lsdo_child, count_child_dirs); + for (exponent = 1; max_size / exponent > 0; exponent *= 10) { + ls3_stats_counting_sort(lsdo_child, count_child_dirs, exponent); + } +} + /* ls3_stats_get_dots - Generates dots to display * depth in .out format reports. */ @@ -415,6 +519,11 @@ static void ls3_stats_prepare_dir_recursive(struct ls3_stats_dir_general *stats, *total_alloc_size += allocate_dir_size; } + /* If there is more than 1 child directory, sorting is required. */ + if (dir_ptr->lsdo_last_child > 0) + ls3_stats_radix_sort(dir_ptr->lsdo_child, + dir_ptr->lsdo_last_child); + /* Add in the LS3_STATS_TYPE_DIRECTORY_SIZE_KB table. * This table includes only directories from this report, i.e. only * those that are less than the maximum declared depth -- 1.8.3.1