bitmap.c (e8b8e97f91b80f08a2f1b7ea4f81e7af61b2cc2f) bitmap.c (d3624466b56dd5b1886c1dff500525b544c19c83)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 *
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
5 *
6 * This code builds two trees of free clusters extents.
7 * Trees are sorted by start of extent and by length of extent.
8 * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees.

--- 15 unchanged lines hidden (view full) ---

24 */
25#define NTFS_MAX_WND_EXTENTS (32u * 1024u)
26
27struct rb_node_key {
28 struct rb_node node;
29 size_t key;
30};
31
1// SPDX-License-Identifier: GPL-2.0
2/*
3 *
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
5 *
6 * This code builds two trees of free clusters extents.
7 * Trees are sorted by start of extent and by length of extent.
8 * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees.

--- 15 unchanged lines hidden (view full) ---

24 */
25#define NTFS_MAX_WND_EXTENTS (32u * 1024u)
26
27struct rb_node_key {
28 struct rb_node node;
29 size_t key;
30};
31
32/* Tree is sorted by start (key). */
33struct e_node {
34 struct rb_node_key start; /* Tree sorted by start. */
35 struct rb_node_key count; /* Tree sorted by len. */
36};
37
38static int wnd_rescan(struct wnd_bitmap *wnd);
39static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw);
40static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits);

--- 1071 unchanged lines hidden (view full) ---

1112
1113 b_len = e->count.key;
1114 b_pos = e->start.key;
1115
1116scan_bitmap:
1117 sb = wnd->sb;
1118 log2_bits = sb->s_blocksize_bits + 3;
1119
32struct e_node {
33 struct rb_node_key start; /* Tree sorted by start. */
34 struct rb_node_key count; /* Tree sorted by len. */
35};
36
37static int wnd_rescan(struct wnd_bitmap *wnd);
38static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw);
39static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits);

--- 1071 unchanged lines hidden (view full) ---

1111
1112 b_len = e->count.key;
1113 b_pos = e->start.key;
1114
1115scan_bitmap:
1116 sb = wnd->sb;
1117 log2_bits = sb->s_blocksize_bits + 3;
1118
1120 /* At most two ranges [hint, max_alloc) + [0, hint) */
1119 /* At most two ranges [hint, max_alloc) + [0, hint). */
1121Again:
1122
1123 /* TODO: Optimize request for case nbits > wbits. */
1124 iw = hint >> log2_bits;
1125 wbits = sb->s_blocksize * 8;
1126 wpos = hint & (wbits - 1);
1127 prev_tail = 0;
1128 fbits_valid = true;

--- 107 unchanged lines hidden (view full) ---

1236 }
1237
1238 /* Increase 'prev_tail' and process next window. */
1239 prev_tail += wbits;
1240 wpos = 0;
1241 continue;
1242 }
1243
1120Again:
1121
1122 /* TODO: Optimize request for case nbits > wbits. */
1123 iw = hint >> log2_bits;
1124 wbits = sb->s_blocksize * 8;
1125 wpos = hint & (wbits - 1);
1126 prev_tail = 0;
1127 fbits_valid = true;

--- 107 unchanged lines hidden (view full) ---

1235 }
1236
1237 /* Increase 'prev_tail' and process next window. */
1238 prev_tail += wbits;
1239 wpos = 0;
1240 continue;
1241 }
1242
1244 /* Read window */
1243 /* Read window. */
1245 bh = wnd_map(wnd, iw);
1246 if (IS_ERR(bh)) {
1247 // TODO: Error.
1248 prev_tail = 0;
1249 wpos = 0;
1250 continue;
1251 }
1252

--- 242 unchanged lines hidden --- 		1244 bh = wnd_map(wnd, iw);
1245 if (IS_ERR(bh)) {
1246 // TODO: Error.
1247 prev_tail = 0;
1248 wpos = 0;
1249 continue;
1250 }
1251

--- 242 unchanged lines hidden ---