From nobody Tue Apr 7 05:58:57 2026 Received: from mail-yx1-f47.google.com (mail-yx1-f47.google.com [74.125.224.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2CFD130DEA6 for ; Mon, 16 Mar 2026 02:19:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.224.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773627600; cv=none; b=AzTwzDuhZG2BnLob70eF6DMXlTtMIMk1fmopqLQAZYkYqVg8gcknsQ0OhEPTlhPvafjMVHkctebGFs4iZZIOxSksbS3NWNjK0V55A9P+Om7oyCpDxWThvmwnj9CERsDRGOfM00RGkaBD8Vu6QkAPipRjdUi06DZCEnDQ6lqBpTE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773627600; c=relaxed/simple; bh=LKbNz4jgNvWd0WXarTRp7UuOBIcqVhVPaKZABGufDM8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=HKP5zOFDFBy/WD7mAajLmXMtUlnpkDmNTz3wjjmfnt3ecjAlSh4g0UDF/1wfhb/Bh3UavSg6YrYsnU6Giu2/0K/ccV9P6dp22IifHsioJ7lXQpHRjcLYj4+YZysDpxt6j4Z1zgvHUgsIossS3B4WXuRPAU2nWBjU73wwqQ8aPlA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dubeyko.com; spf=pass smtp.mailfrom=dubeyko.com; dkim=pass (2048-bit key) header.d=dubeyko-com.20230601.gappssmtp.com header.i=@dubeyko-com.20230601.gappssmtp.com header.b=s6JW3EdT; arc=none smtp.client-ip=74.125.224.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dubeyko.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=dubeyko.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=dubeyko-com.20230601.gappssmtp.com header.i=@dubeyko-com.20230601.gappssmtp.com header.b="s6JW3EdT" Received: by mail-yx1-f47.google.com with SMTP id 956f58d0204a3-64c9a6d7f81so3973533d50.3 for ; Sun, 15 Mar 2026 19:19:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dubeyko-com.20230601.gappssmtp.com; s=20230601; t=1773627595; x=1774232395; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=oKbLxfQ7PMyCY2trXnORKfnxYDPCiSg+ux2upmRPiKA=; b=s6JW3EdTjO8ybr7nF5rwNoz1o5TquIoVLE6NMDKfjDbs/Cn51YqB/m/c7uHH6dAbXS FRDZq8HBHSMgELguXHuyuj9GqIXfDvxyErIa/l5wB03NcgFSFUxwfGNuevytnr3GpsIN CVMDY+DnqLLr5S7bBYUTXbbTFs1bAoHRpVTali+3wrc5xTlW6adkGWEyrYnIbv/ZCBEa WH6alCTBdIuR5cwiPT1MIzYTWZbwTZewls8XiMGcnSWpT9h+KVp7pqL5dpbuFAIDZWmx dEAnjP4vOKxhTgW+rKrjOc0NfF/eZEsJBz9/D8pkbazEnZC+LZ65CurKDxrkHRFnXkkD ehDA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1773627595; x=1774232395; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=oKbLxfQ7PMyCY2trXnORKfnxYDPCiSg+ux2upmRPiKA=; b=H12mOzsPC8nLwx0WHnL7XhO4IO91CmO8K+35bNFEjwBAXvGwqqWUaQJWp8kuvRyVHZ HKuih+EqxbjkYL7HER9J+i68yx/47W/YKpdSFfgN3a9h3l/ezxttWbtGNcGXA24CjV2Y Hz6Irsv36R9GPkMfYC1a8Ig+p6s2nRZuU9PW84WGQ2R+1gtj6+eUXQ19Rjn0HKQVitow x3jlA6159g37xsW9dNLknCFAUHr9FN8NIO+Y6g3faqbCT2fqiI+pzvKb0dz3zERYKciB uUvngouadT3HTIkHEAbcPVJJUkcNUq9zznQKaMiinRle+CGkrS4kEWEYW/Wm2u0DpzRA nFWQ== X-Gm-Message-State: AOJu0YywajcmcfHYKp/9ONr1ROkRneX1PNezVf2bCbRr1i+jWJ03xdk1 PIGTbZ2E+s3TkET1OFOdsWZdHDRlX57WHQa9GEmdafV+qY3I44GnxXlGXTb2jvr10y4= X-Gm-Gg: ATEYQzwn9Drv4/b32Bas1Ilo5Pbx0eDfS373pd0XY82/laEFgMzypprpUVG/LK+ZEWU A9mNYk8v1VidMpcQ6zhCCG5dew6JrOA7quA5pht6/HqP+hFEtK30tPdMK48ufZmdaaN1x4rlVJk Hl+GE60jqclTxweZax7+ULLTgz6Bm4kHaftOoeEtgO8okIN4X0QOdzHffPWEnxPbK75WY0iEVZO mUz2gQa5mQd9E7P3Aph1H2N3oBZeKWAnCjuTHoxJonTaB08Zui++0Xv3v9UDT/b4zNQmvDxZwL8 r6fp8sBYQH/04jJaxrVCqX3UW2Zoo6BXGa5ltj4KvgZbPqKBE8eF/w8ByTSG0vIAHFUkHlSBB83 zsi8vWD6ZerMgUuI3lRl/QwSsAArxJYr5BeB3vhZ9BjIe90jHZEf8F6fkTnE2/iOvTAEdihaZGC ZDmAQSXSQcC9aA/YXjAkuGI84++/7g6IsdLOT4Pfo0SuZY0OZmM/1BFSOOtydRnPbtUgensmXHG 2/0flpXZLYCL3H0QN+fSVDwtJNLB7uLN4Y= X-Received: by 2002:a05:690c:6d83:b0:79a:2ea7:36b7 with SMTP id 00721157ae682-79a2ea74f62mr71656917b3.51.1773627595063; Sun, 15 Mar 2026 19:19:55 -0700 (PDT) Received: from pop-os.attlocal.net ([2600:1700:6476:1430:6939:3e01:5e8f:6093]) by smtp.gmail.com with ESMTPSA id 00721157ae682-79917deb69asm79721617b3.10.2026.03.15.19.19.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Mar 2026 19:19:54 -0700 (PDT) From: Viacheslav Dubeyko To: linux-fsdevel@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Viacheslav Dubeyko Subject: [PATCH v2 57/79] ssdfs: introduce invalidated extents b-tree Date: Sun, 15 Mar 2026 19:17:51 -0700 Message-ID: <20260316021800.1694650-25-slava@dubeyko.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260316021800.1694650-1-slava@dubeyko.com> References: <20260316021800.1694650-1-slava@dubeyko.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Complete patchset is available here: https://github.com/dubeyko/ssdfs-driver/tree/master/patchset/linux-kernel-6= .18.0 ZNS SSD operates by zone concept. Zone can be: (1) empty, (2) open (implicitly or explicitly), (3) closed, (4) full. The number of open/active zones is limited by some threshold. To manage open/active zones limitation, SSDFS has current user data segment for new data and current user data segment to receive updates for closed zones. Every update of data in closed zone requires: (1) store updated data into current segment for updated user data, (2) update extents b-tree by new data location, (3) add invalidated extent of closed zone into invalidated extents b-tree. Invalidated extents b-tree is responsible for: (1) correct erase block's (closed zone) block bitmap by means of setting moved logical blocks as invalidated during erase block object initialization, (2) collect all invalidated extents of closed zone. If the length of all closed zone's invalidated extents is equal to zone size, then closed zone can be re-initialized or be erased. Signed-off-by: Viacheslav Dubeyko --- fs/ssdfs/invalidated_extents_tree.h | 96 +++++++++++++++++++++++++++++ 1 file changed, 96 insertions(+) create mode 100644 fs/ssdfs/invalidated_extents_tree.h diff --git a/fs/ssdfs/invalidated_extents_tree.h b/fs/ssdfs/invalidated_ext= ents_tree.h new file mode 100644 index 000000000000..a0d1993e5523 --- /dev/null +++ b/fs/ssdfs/invalidated_extents_tree.h @@ -0,0 +1,96 @@ +/* + * SPDX-License-Identifier: BSD-3-Clause-Clear + * + * SSDFS -- SSD-oriented File System. + * + * fs/ssdfs/invalidated_extents_tree.h - invalidated extents btree declara= tions. + * + * Copyright (c) 2022-2026 Viacheslav Dubeyko + * http://www.ssdfs.org/ + * Copyright (c) 2022-2023 Bytedance Ltd. and/or its affiliates. + * https://www.bytedance.com/ + * All rights reserved. + * + * Authors: Viacheslav Dubeyko + * + * Acknowledgement: Cong Wang + */ + +#ifndef _SSDFS_INVALIDATED_EXTENTS_TREE_H +#define _SSDFS_INVALIDATED_EXTENTS_TREE_H + +/* + * struct ssdfs_invextree_info - invalidated extents tree object + * @state: invalidated extents btree state + * @lock: invalidated extents btree lock + * @generic_tree: generic btree description + * @extents_count: count of extents in the whole tree + * @fsi: pointer on shared file system object + */ +struct ssdfs_invextree_info { + atomic_t state; + struct rw_semaphore lock; + struct ssdfs_btree generic_tree; + + atomic64_t extents_count; + + struct ssdfs_fs_info *fsi; +}; + +/* Invalidated extents tree states */ +enum { + SSDFS_INVEXTREE_UNKNOWN_STATE, + SSDFS_INVEXTREE_CREATED, + SSDFS_INVEXTREE_INITIALIZED, + SSDFS_INVEXTREE_DIRTY, + SSDFS_INVEXTREE_CORRUPTED, + SSDFS_INVEXTREE_STATE_MAX +}; + +/* + * Invalidated extents tree API + */ +int ssdfs_invextree_create(struct ssdfs_fs_info *fsi); +void ssdfs_invextree_destroy(struct ssdfs_fs_info *fsi); +int ssdfs_invextree_flush(struct ssdfs_fs_info *fsi); + +int ssdfs_invextree_find(struct ssdfs_invextree_info *tree, + struct ssdfs_raw_extent *extent, + struct ssdfs_btree_search *search); +int ssdfs_invextree_add(struct ssdfs_invextree_info *tree, + struct ssdfs_raw_extent *extent, + struct ssdfs_btree_search *search); +int ssdfs_invextree_delete(struct ssdfs_invextree_info *tree, + struct ssdfs_raw_extent *extent, + struct ssdfs_btree_search *search); + +/* + * Invalidated extents tree's internal API + */ +int ssdfs_invextree_find_leaf_node(struct ssdfs_invextree_info *tree, + u64 seg_id, + struct ssdfs_btree_search *search); +int ssdfs_invextree_get_start_hash(struct ssdfs_invextree_info *tree, + u64 *start_hash); +int ssdfs_invextree_node_hash_range(struct ssdfs_invextree_info *tree, + struct ssdfs_btree_search *search, + u64 *start_hash, u64 *end_hash, + u16 *items_count); +int ssdfs_invextree_extract_range(struct ssdfs_invextree_info *tree, + u16 start_index, u16 count, + struct ssdfs_btree_search *search); +int ssdfs_invextree_check_search_result(struct ssdfs_btree_search *search); +int ssdfs_invextree_get_next_hash(struct ssdfs_invextree_info *tree, + struct ssdfs_btree_search *search, + u64 *next_hash); + +void ssdfs_debug_invextree_object(struct ssdfs_invextree_info *tree); + +/* + * Invalidated extents btree specialized operations + */ +extern const struct ssdfs_btree_descriptor_operations ssdfs_invextree_desc= _ops; +extern const struct ssdfs_btree_operations ssdfs_invextree_ops; +extern const struct ssdfs_btree_node_operations ssdfs_invextree_node_ops; + +#endif /* _SSDFS_INVALIDATED_EXTENTS_TREE_H */ --=20 2.34.1