GNU logs - #77441, boring messages

Message sent to leo@HIDDEN, w@HIDDEN, guix-patches@HIDDEN:

Subject: [bug#77441] [PATCH] gnu: compsize: Remove.
Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: leo@HIDDEN, w@HIDDEN, guix-patches@HIDDEN
Resent-Date: Tue, 01 Apr 2025 22:31:02 +0000
Resent-Message-ID: <handler.77441.B.174354663919973 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 77441 <at> debbugs.gnu.org
Cc: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>, Ashish SHUKLA <ashish.is@HIDDEN>, Leo Famulari <leo@HIDDEN>, Wilko Meyer <w@HIDDEN>
From: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>
Date: Wed,  2 Apr 2025 00:30:13 +0200
Message-ID: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

This package fails to build with btrfs-progs@HIDDEN and hasn’t seen any
activity upstream since Dec. 2023.

* gnu/packages/linux.scm (compsize): Remove.

Change-Id: I30513d8fbda362c49c763300db7a7ff41e81a38c
---
 gnu/packages/linux.scm | 44 ------------------------------------------
 1 file changed, 44 deletions(-)

Hi,

The ‘compsize’ package fails to build since the e2fsprogs and btrfs-progs
upgrades from <https://issues.guix.gnu.org/75119> (commit
7cef57e2a7dedd3eea0ba5852915eaf10f00e9f4).

According to the deprecation policy, this patch can be applied in one month
if there are no objections, on May 2nd.

Ludo’.

diff --git a/gnu/packages/linux.scm b/gnu/packages/linux.scm
index 2c587baac0..7fa36306cc 100644
--- a/gnu/packages/linux.scm
+++ b/gnu/packages/linux.scm
@@ -6887,50 +6887,6 @@ (define-public cramfs-tools
 blocks and random block placement.")
     (license license:gpl2+)))

-(define-public compsize
-  (package
-    (name "compsize")
-    (version "1.5")
-    (home-page "https://github.com/kilobyte/compsize")
-    (source (origin
-              (method git-fetch)
-              (uri (git-reference
-                    (url home-page)
-                    (commit (string-append "v" version))))
-              (sha256
-               (base32 "0vqnrwgpv6pc1yjl0g4gl71xyl6v0xl3pyqjanjpwps73c53azir"))
-              (file-name (git-file-name name version))))
-    (build-system gnu-build-system)
-    (inputs
-     (list btrfs-progs))
-    (arguments
-     `(#:tests? #f                      ; No tests.
-       #:make-flags
-       (list (string-append "CC=" ,(cc-for-target)))
-       #:phases
-       (modify-phases %standard-phases
-         (delete 'configure)
-         (replace 'install
-           (lambda* (#:key outputs #:allow-other-keys)
-             (let ((out (assoc-ref outputs "out")))
-               (install-file "compsize" (string-append out "/bin"))
-               (install-file "compsize.8" (string-append out "/share/man/man8"))))))))
-    (synopsis "Find compression type/ratio on Btrfs files")
-    (description "@command{compsize} takes a list of files (given as
-arguments) on a Btrfs file system and measures used compression types and
-effective compression ratio, producing a report.
-
-A directory has no extents but has a (recursive) list of files.  A non-regular
-file is silently ignored.
-
-As it makes no sense to talk about compression ratio of a partial extent,
-every referenced extent is counted whole, exactly once -- no matter if you use
-only a few bytes of a 1GB extent or reflink it a thousand times.  Thus, the
-uncompressed size will not match the number given by @command{tar} or
-@command{du}.  On the other hand, the space used should be accurate (although
-obviously it can be shared with files outside our set).")
-    (license license:gpl2+)))
-
 (define-public f2fs-tools
   (package
     (name "f2fs-tools")

base-commit: eb04a0d2c955f5fa9a721537c8202fc5c5959b19
-- 
2.49.0

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>
Subject: bug#77441: Acknowledgement ([PATCH] gnu: compsize: Remove.)
Message-ID: <handler.77441.B.174354663919973.ack <at> debbugs.gnu.org>
References: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
X-Gnu-PR-Message: ack 77441
X-Gnu-PR-Package: guix-patches
X-Gnu-PR-Keywords: patch
Reply-To: 77441 <at> debbugs.gnu.org
Date: Tue, 01 Apr 2025 22:31:02 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

As you requested using X-Debbugs-CC, your message was also forwarded to
  Leo Famulari <leo@HIDDEN>, Wilko Meyer <w@HIDDEN>
(after having been given a bug report number, if it did not have one).

Your message has been sent to the package maintainer(s):
 guix-patches@HIDDEN

If you wish to submit further information on this problem, please
send it to 77441 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
77441: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D77441
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to guix-patches@HIDDEN:

Subject: [bug#77441] [PATCH] gnu: compsize: Remove.
Resent-From: Greg Hogan <code@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: guix-patches@HIDDEN
Resent-Date: Tue, 15 Apr 2025 19:00:10 +0000
Resent-Message-ID: <handler.77441.B77441.174474355328636 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>
Cc: 77441 <at> debbugs.gnu.org, Wilko Meyer <w@HIDDEN>, Ashish SHUKLA <ashish.is@HIDDEN>, Leo Famulari <leo@HIDDEN>
MIME-Version: 1.0
References: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
In-Reply-To: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
From: Greg Hogan <code@HIDDEN>
Date: Tue, 15 Apr 2025 14:58:49 -0400
Message-ID: <CA+3U0Zn1UY=K8xHXbR77FkqnPm8PbSuZ+u0cMtmVz4Hpk+J6_w@HIDDEN>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

On Tue, Apr 1, 2025 at 6:31=E2=80=AFPM Ludovic Court=C3=A8s <ludo@HIDDEN> =
wrote:
>
> This package fails to build with btrfs-progs@HIDDEN and hasn=E2=80=99t see=
n any
> activity upstream since Dec. 2023.

I am sending a patch from upstream's issues!

The breakage is reported to have occurred in btrfs-progs 6.10. Guix
upgraded from 6.3.3 to 6.13 on April 1st, and my profile is still on
the older version due to other broken packages.

Greg

Message sent to leo@HIDDEN, w@HIDDEN, guix-patches@HIDDEN:

Subject: [bug#77441] [PATCH] gnu: compsize: Update and fix build.
References: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
In-Reply-To: <ba9278c75b021a416b44d0f50c6c379194ba2607.1743546397.git.ludo@HIDDEN>
Resent-From: Greg Hogan <code@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: leo@HIDDEN, w@HIDDEN, guix-patches@HIDDEN
Resent-Date: Tue, 15 Apr 2025 19:03:08 +0000
Resent-Message-ID: <handler.77441.B77441.1744743726736 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 77441 <at> debbugs.gnu.org
Cc: Greg Hogan <code@HIDDEN>, Leo Famulari <leo@HIDDEN>, Wilko Meyer <w@HIDDEN>
From: Greg Hogan <code@HIDDEN>
Date: Tue, 15 Apr 2025 19:00:47 +0000
Message-ID: <d363eb170c1865ddf95bef2581722c675c8fea27.1744742607.git.code@HIDDEN>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

* gnu/packages/linux.scm (compsize): Update to d79eacf7.
[source]<patches>: Add compsize-fix-btrfs-progs-compatibility.patch.
* gnu/packages/patches/compsize-fix-btrfs-progs-compatibility.patch:
New file.
* gnu/local.mk (dist_patch_DATA): Update accordingly.

Change-Id: Ia967635c2fce035ebf7e4067a2dd412d4f7a0467
---
 gnu/local.mk                                  |    1 +
 gnu/packages/linux.scm                        |   65 +-
 ...mpsize-fix-btrfs-progs-compatibility.patch | 1614 +++++++++++++++++
 3 files changed, 1650 insertions(+), 30 deletions(-)
 create mode 100644 gnu/packages/patches/compsize-fix-btrfs-progs-compatibility.patch

diff --git a/gnu/local.mk b/gnu/local.mk
index 64ac95e8d1..aa85cf9c55 100644
--- a/gnu/local.mk
+++ b/gnu/local.mk
@@ -1136,6 +1136,7 @@ dist_patch_DATA =						\
   %D%/packages/patches/collectd-5.11.0-noinstallvar.patch		\
   %D%/packages/patches/combinatorial-blas-awpm.patch		\
   %D%/packages/patches/combinatorial-blas-io-fix.patch		\
+  %D%/packages/patches/compsize-fix-btrfs-progs-compatibility.patch	\
   %D%/packages/patches/containerd-create-pid-file.patch	\
   %D%/packages/patches/converseen-hide-updates-checks.patch	\
   %D%/packages/patches/converseen-hide-non-free-pointers.patch	\
diff --git a/gnu/packages/linux.scm b/gnu/packages/linux.scm
index b147f74d39..3b79bf02c7 100644
--- a/gnu/packages/linux.scm
+++ b/gnu/packages/linux.scm
@@ -6900,35 +6900,40 @@ (define-public cramfs-tools
     (license license:gpl2+)))
 
 (define-public compsize
-  (package
-    (name "compsize")
-    (version "1.5")
-    (home-page "https://github.com/kilobyte/compsize")
-    (source (origin
-              (method git-fetch)
-              (uri (git-reference
-                    (url home-page)
-                    (commit (string-append "v" version))))
-              (sha256
-               (base32 "0vqnrwgpv6pc1yjl0g4gl71xyl6v0xl3pyqjanjpwps73c53azir"))
-              (file-name (git-file-name name version))))
-    (build-system gnu-build-system)
-    (inputs
-     (list btrfs-progs))
-    (arguments
-     `(#:tests? #f                      ; No tests.
-       #:make-flags
-       (list (string-append "CC=" ,(cc-for-target)))
-       #:phases
-       (modify-phases %standard-phases
-         (delete 'configure)
-         (replace 'install
-           (lambda* (#:key outputs #:allow-other-keys)
-             (let ((out (assoc-ref outputs "out")))
-               (install-file "compsize" (string-append out "/bin"))
-               (install-file "compsize.8" (string-append out "/share/man/man8"))))))))
-    (synopsis "Find compression type/ratio on Btrfs files")
-    (description "@command{compsize} takes a list of files (given as
+  (let ((version "1.5")
+        (commit "d79eacf77abe3b799387bb8a4e07a18f1f1031e8")
+        (revision "0"))
+    (package
+      (name "compsize")
+      (version (git-version version revision commit))
+      (home-page "https://github.com/kilobyte/compsize")
+      (source (origin
+                (method git-fetch)
+                (uri (git-reference
+                      (url home-page)
+                      (commit commit)))
+                (sha256
+                 (base32 "02fvgy12m50rg1snp555a1kc3cm01g2imb81cih7ikhkbjbca0d7"))
+                (file-name (git-file-name name version))
+                (patches
+                 (search-patches "compsize-fix-btrfs-progs-compatibility.patch"))))
+      (build-system gnu-build-system)
+      (inputs
+       (list btrfs-progs))
+      (arguments
+       `(#:tests? #f                      ; No tests.
+         #:make-flags
+         (list (string-append "CC=" ,(cc-for-target)))
+         #:phases
+         (modify-phases %standard-phases
+           (delete 'configure)
+           (replace 'install
+             (lambda* (#:key outputs #:allow-other-keys)
+               (let ((out (assoc-ref outputs "out")))
+                 (install-file "compsize" (string-append out "/bin"))
+                 (install-file "compsize.8" (string-append out "/share/man/man8"))))))))
+      (synopsis "Find compression type/ratio on Btrfs files")
+      (description "@command{compsize} takes a list of files (given as
 arguments) on a Btrfs file system and measures used compression types and
 effective compression ratio, producing a report.
 
@@ -6941,7 +6946,7 @@ (define-public compsize
 uncompressed size will not match the number given by @command{tar} or
 @command{du}.  On the other hand, the space used should be accurate (although
 obviously it can be shared with files outside our set).")
-    (license license:gpl2+)))
+      (license license:gpl2+))))
 
 (define-public f2fs-tools
   (package
diff --git a/gnu/packages/patches/compsize-fix-btrfs-progs-compatibility.patch b/gnu/packages/patches/compsize-fix-btrfs-progs-compatibility.patch
new file mode 100644
index 0000000000..8bb28d125d
--- /dev/null
+++ b/gnu/packages/patches/compsize-fix-btrfs-progs-compatibility.patch
@@ -0,0 +1,1614 @@
+From upstream from https://github.com/kilobyte/compsize/pull/53
+
+From c4f18f6af6a0e0872f0ae9de5b90b799cbdd0f12 Mon Sep 17 00:00:00 2001
+From: Justin Brewer <jbrewer90@HIDDEN>
+Date: Sun, 24 Nov 2024 23:10:54 -0600
+Subject: [PATCH] Replace radix_tree with a bitmap
+
+New versions of btrfs-progs dropped radix_tree and made incompatible
+changes to kerncompat.h. radix_tree was overkill, since it was only
+used to track if a page had been seen before.
+
+Replace radix_tree with a simple bitmap, and drop the broken imported
+source files.
+
+Signed-off-by: Justin Brewer <jbrewer90@HIDDEN>
+---
+ Makefile     |   2 +-
+ bitmap.c     |  70 +++++
+ bitmap.h     |  28 ++
+ compsize.c   |  34 ++-
+ kerncompat.h | 399 ------------------------
+ radix-tree.c | 849 ---------------------------------------------------
+ radix-tree.h |  97 ------
+ 7 files changed, 125 insertions(+), 1354 deletions(-)
+ create mode 100644 bitmap.c
+ create mode 100644 bitmap.h
+ delete mode 100644 kerncompat.h
+ delete mode 100644 radix-tree.c
+ delete mode 100644 radix-tree.h
+
+diff --git a/Makefile b/Makefile
+index af6cf8b..6429fb4 100644
+--- a/Makefile
++++ b/Makefile
+@@ -1,6 +1,6 @@
+ PREFIX ?= /usr
+ CC ?= gcc
+-CFLAGS ?= -Wall -std=gnu90
++CFLAGS ?= -Wall -std=gnu90 -D_GNU_SOURCE
+ SRC_DIR := $(dir $(lastword $(MAKEFILE_LIST)))
+ 
+ 
+diff --git a/bitmap.c b/bitmap.c
+new file mode 100644
+index 0000000..e044fab
+--- /dev/null
++++ b/bitmap.c
+@@ -0,0 +1,70 @@
++#include "bitmap.h"
++
++#include <errno.h>
++#include <stddef.h>
++#include <stdint.h>
++#include <stdlib.h>
++#include <sys/mman.h>
++
++#define CHUNK_SHIFT 21 /* 2MiB */
++#define WORD_SHIFT 5
++#define WORD_MASK ((1 << WORD_SHIFT) - 1)
++#define BIT_TO_CHUNK(_b) ((_b) >> CHUNK_SHIFT)
++#define BIT_TO_WORD(_b) ((_b) >> WORD_SHIFT)
++#define BIT_TO_MASK(_b) (1 << ((_b) & WORD_MASK))
++#define MAP_SIZE(_s) ((_s) * (1 << CHUNK_SHIFT))
++
++static int resize(struct bitmap *b, size_t new_size)
++{
++	if(new_size <= b->size)
++		return 0;
++
++	void *new_map = mremap(b->map, MAP_SIZE(b->size), MAP_SIZE(new_size),
++			MREMAP_MAYMOVE);
++
++	if(new_map == MAP_FAILED)
++		return -ENOMEM;
++
++	b->map = new_map;
++	b->size = new_size;
++	return 0;
++}
++
++int bitmap_init(struct bitmap *b)
++{
++	b->size = 1;
++	b->map = mmap(NULL, MAP_SIZE(b->size), PROT_READ | PROT_WRITE,
++			MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
++	return b->map == MAP_FAILED;
++}
++
++void bitmap_destroy(struct bitmap *b)
++{
++	munmap(b->map, MAP_SIZE(b->size));
++}
++
++/**
++ * Mark and return previous value of a bit
++ *
++ * Resizes map if necessary. Returns -ENOMEM if resize fails.
++ */
++int bitmap_mark(struct bitmap *b, size_t bit)
++{
++	int rv;
++	size_t chunk, word, mask;
++
++	chunk = BIT_TO_CHUNK(bit);
++	word = BIT_TO_WORD(bit);
++	mask = BIT_TO_MASK(bit);
++
++	rv = resize(b, chunk + 1);
++
++	if(rv)
++		return rv;
++
++	if(b->map[word] & mask)
++		return 1;
++
++	b->map[word] |= mask;
++	return 0;
++}
+diff --git a/bitmap.h b/bitmap.h
+new file mode 100644
+index 0000000..f2f05d4
+--- /dev/null
++++ b/bitmap.h
+@@ -0,0 +1,28 @@
++#ifndef COMPSIZE__BITMAP_H__
++#define COMPSIZE__BITMAP_H__
++
++#include <stddef.h>
++#include <stdint.h>
++
++/**
++ * Simple pseudo-sparse bitmap
++ *
++ * Storage is mmaped to take advantage of lazy page allocation. Automatically
++ * resizes when accessing bits past the end of the current storage.
++ *
++ * Worst case memory usage 32MiB per TiB of 4K filesystem extents.
++ *
++ * @map: Word storage of bitmap
++ * @size: Size of map, as number of 2MiB chunks
++ */
++struct bitmap
++{
++    uint32_t *map;
++    size_t size;
++};
++
++int bitmap_init(struct bitmap *b);
++void bitmap_destroy(struct bitmap *b);
++int bitmap_mark(struct bitmap *b, size_t bit);
++
++#endif
+diff --git a/compsize.c b/compsize.c
+index 42ec304..dcb099f 100644
+--- a/compsize.c
++++ b/compsize.c
+@@ -14,7 +14,9 @@
+ #include <linux/limits.h>
+ #include <getopt.h>
+ #include <signal.h>
+-#include "radix-tree.h"
++#include <errno.h>
++#include <string.h>
++#include "bitmap.h"
+ #include "endianness.h"
+ 
+ #if defined(DEBUG)
+@@ -50,7 +52,7 @@ struct workspace
+         uint64_t nfiles;
+         uint64_t nextents, nrefs, ninline, nfrag;
+         uint64_t fragend;
+-        struct radix_tree_root seen_extents;
++        struct bitmap seen_extents;
+ };
+ 
+ static const char *comp_types[MAX_ENTRIES] = { "none", "zlib", "lzo", "zstd" };
+@@ -93,6 +95,11 @@ static void init_sv2_args(ino_t st_ino, struct btrfs_sv2_args *sv2_args)
+         sv2_args->buf_size = sizeof(sv2_args->buf);
+ }
+ 
++static inline int IS_ALIGNED(uintptr_t ptr, size_t align)
++{
++	return (ptr & (align - 1)) == 0;
++}
++
+ static inline int is_hole(uint64_t disk_bytenr)
+ {
+     return disk_bytenr == 0;
+@@ -105,6 +112,7 @@ static void parse_file_extent_item(uint8_t *bp, uint32_t hlen,
+     uint64_t disk_num_bytes, ram_bytes, disk_bytenr, num_bytes;
+     uint32_t inline_header_sz;
+     unsigned  comp_type;
++    int rv;
+ 
+     DPRINTF("len=%u\n", hlen);
+ 
+@@ -152,15 +160,20 @@ static void parse_file_extent_item(uint8_t *bp, uint32_t hlen,
+     if (!IS_ALIGNED(disk_bytenr, 1 << 12))
+         die("%s: Extent not 4K-aligned at %"PRIu64"?!?\n", filename, disk_bytenr);
+ 
+-    unsigned long pageno = disk_bytenr >> 12;
+-    radix_tree_preload(GFP_KERNEL);
+-    if (radix_tree_insert(&ws->seen_extents, pageno, (void *)pageno) == 0)
++    switch((rv = bitmap_mark(&ws->seen_extents, disk_bytenr >> 12)))
+     {
++    case 0:
+          ws->disk[comp_type] += disk_num_bytes;
+          ws->uncomp[comp_type] += ram_bytes;
+          ws->nextents++;
++         break;
++    case 1:
++         break;
++    default:
++         errno = -rv;
++         die("bitmak_mark: %m\n");
+     }
+-    radix_tree_preload_end();
++
+     ws->refd[comp_type] += num_bytes;
+     ws->nrefs++;
+ 
+@@ -439,6 +452,7 @@ static int print_stats(struct workspace *ws)
+ 
+ int main(int argc, char **argv)
+ {
++    int rv;
+     struct workspace *ws;
+ 
+     ws = (struct workspace *) calloc(sizeof(*ws), 1);
+@@ -451,8 +465,11 @@ int main(int argc, char **argv)
+         return 1;
+     }
+ 
+-    radix_tree_init();
+-    INIT_RADIX_TREE(&ws->seen_extents, 0);
++    if((rv = bitmap_init(&ws->seen_extents))) {
++        errno = -rv;
++        die("bitmap_init: %m\n");
++    }
++
+     signal(SIGUSR1, sigusr1);
+ 
+     for (; argv[optind]; optind++)
+@@ -460,6 +477,7 @@ int main(int argc, char **argv)
+ 
+     int ret = print_stats(ws);
+ 
++    bitmap_destroy(&ws->seen_extents);
+     free(ws);
+ 
+     return ret;
+diff --git a/kerncompat.h b/kerncompat.h
+deleted file mode 100644
+index 6ad35ea..0000000
+--- a/kerncompat.h
++++ /dev/null
+@@ -1,399 +0,0 @@
+-/*
+- * Copyright (C) 2007 Oracle.  All rights reserved.
+- *
+- * This program is free software; you can redistribute it and/or
+- * modify it under the terms of the GNU General Public
+- * License v2 as published by the Free Software Foundation.
+- *
+- * This program is distributed in the hope that it will be useful,
+- * but WITHOUT ANY WARRANTY; without even the implied warranty of
+- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+- * General Public License for more details.
+- *
+- * You should have received a copy of the GNU General Public
+- * License along with this program; if not, write to the
+- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+- * Boston, MA 021110-1307, USA.
+- */
+-
+-#ifndef __KERNCOMPAT_H__
+-#define __KERNCOMPAT_H__
+-
+-#include <stdio.h>
+-#include <stdlib.h>
+-#include <errno.h>
+-#include <string.h>
+-#include <endian.h>
+-#include <byteswap.h>
+-#include <assert.h>
+-#include <stddef.h>
+-#include <linux/types.h>
+-#include <stdint.h>
+-
+-#include <features.h>
+-
+-#ifndef __GLIBC__
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-#define BTRFS_DISABLE_BACKTRACE
+-#endif
+-#define __always_inline __inline __attribute__ ((__always_inline__))
+-#endif
+-
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-#include <execinfo.h>
+-#endif
+-
+-#define ptr_to_u64(x)	((u64)(uintptr_t)x)
+-#define u64_to_ptr(x)	((void *)(uintptr_t)x)
+-
+-#ifndef READ
+-#define READ 0
+-#define WRITE 1
+-#define READA 2
+-#endif
+-
+-#define gfp_t int
+-#define get_cpu_var(p) (p)
+-#define __get_cpu_var(p) (p)
+-#define BITS_PER_BYTE 8
+-#define BITS_PER_LONG (__SIZEOF_LONG__ * BITS_PER_BYTE)
+-#define __GFP_BITS_SHIFT 20
+-#define __GFP_BITS_MASK ((int)((1 << __GFP_BITS_SHIFT) - 1))
+-#define GFP_KERNEL 0
+-#define GFP_NOFS 0
+-#define __read_mostly
+-#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+-
+-#ifndef ULONG_MAX
+-#define ULONG_MAX       (~0UL)
+-#endif
+-
+-#define __token_glue(a,b,c)	___token_glue(a,b,c)
+-#define ___token_glue(a,b,c)	a ## b ## c
+-#ifdef DEBUG_BUILD_CHECKS
+-#define BUILD_ASSERT(x)		extern int __token_glue(compile_time_assert_,__LINE__,__COUNTER__)[1-2*!(x)] __attribute__((unused))
+-#else
+-#define BUILD_ASSERT(x)
+-#endif
+-
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-#define MAX_BACKTRACE	16
+-static inline void print_trace(void)
+-{
+-	void *array[MAX_BACKTRACE];
+-	int size;
+-
+-	size = backtrace(array, MAX_BACKTRACE);
+-	backtrace_symbols_fd(array, size, 2);
+-}
+-#endif
+-
+-static inline void warning_trace(const char *assertion, const char *filename,
+-			      const char *func, unsigned line, long val)
+-{
+-	if (!val)
+-		return;
+-	fprintf(stderr,
+-		"%s:%d: %s: Warning: assertion `%s` failed, value %ld\n",
+-		filename, line, func, assertion, val);
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-	print_trace();
+-#endif
+-}
+-
+-static inline void bugon_trace(const char *assertion, const char *filename,
+-			      const char *func, unsigned line, long val)
+-{
+-	if (!val)
+-		return;
+-	fprintf(stderr,
+-		"%s:%d: %s: BUG_ON `%s` triggered, value %ld\n",
+-		filename, line, func, assertion, val);
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-	print_trace();
+-#endif
+-	abort();
+-	exit(1);
+-}
+-
+-#ifdef __CHECKER__
+-#define __force    __attribute__((force))
+-#define __bitwise__ __attribute__((bitwise))
+-#else
+-#define __force
+-#ifndef __bitwise__
+-#define __bitwise__
+-#endif
+-#endif
+-
+-#ifndef __CHECKER__
+-/*
+- * Since we're using primitive definitions from kernel-space, we need to
+- * define __KERNEL__ so that system header files know which definitions
+- * to use.
+- */
+-#define __KERNEL__
+-#include <asm/types.h>
+-typedef __u32 u32;
+-typedef __u64 u64;
+-typedef __u16 u16;
+-typedef __u8 u8;
+-typedef __s64 s64;
+-typedef __s32 s32;
+-
+-/*
+- * Continuing to define __KERNEL__ breaks others parts of the code, so
+- * we can just undefine it now that we have the correct headers...
+- */
+-#undef __KERNEL__
+-#else
+-typedef unsigned int u32;
+-typedef unsigned int __u32;
+-typedef unsigned long long u64;
+-typedef unsigned char u8;
+-typedef unsigned short u16;
+-typedef long long s64;
+-typedef int s32;
+-#endif
+-
+-
+-struct vma_shared { int prio_tree_node; };
+-struct vm_area_struct {
+-	unsigned long vm_pgoff;
+-	unsigned long vm_start;
+-	unsigned long vm_end;
+-	struct vma_shared shared;
+-};
+-
+-struct page {
+-	unsigned long index;
+-};
+-
+-struct mutex {
+-	unsigned long lock;
+-};
+-
+-#define mutex_init(m)						\
+-do {								\
+-	(m)->lock = 1;						\
+-} while (0)
+-
+-static inline void mutex_lock(struct mutex *m)
+-{
+-	m->lock--;
+-}
+-
+-static inline void mutex_unlock(struct mutex *m)
+-{
+-	m->lock++;
+-}
+-
+-static inline int mutex_is_locked(struct mutex *m)
+-{
+-	return (m->lock != 1);
+-}
+-
+-#define cond_resched()		do { } while (0)
+-#define preempt_enable()	do { } while (0)
+-#define preempt_disable()	do { } while (0)
+-
+-#define BITOP_MASK(nr)		(1UL << ((nr) % BITS_PER_LONG))
+-#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
+-
+-#ifndef __attribute_const__
+-#define __attribute_const__	__attribute__((__const__))
+-#endif
+-
+-/**
+- * __set_bit - Set a bit in memory
+- * @nr: the bit to set
+- * @addr: the address to start counting from
+- *
+- * Unlike set_bit(), this function is non-atomic and may be reordered.
+- * If it's called on the same region of memory simultaneously, the effect
+- * may be that only one operation succeeds.
+- */
+-static inline void __set_bit(int nr, volatile unsigned long *addr)
+-{
+-	unsigned long mask = BITOP_MASK(nr);
+-	unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+-
+-	*p  |= mask;
+-}
+-
+-static inline void __clear_bit(int nr, volatile unsigned long *addr)
+-{
+-	unsigned long mask = BITOP_MASK(nr);
+-	unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+-
+-	*p &= ~mask;
+-}
+-
+-/**
+- * test_bit - Determine whether a bit is set
+- * @nr: bit number to test
+- * @addr: Address to start counting from
+- */
+-static inline int test_bit(int nr, const volatile unsigned long *addr)
+-{
+-	return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
+-}
+-
+-/*
+- * error pointer
+- */
+-#define MAX_ERRNO	4095
+-#define IS_ERR_VALUE(x) ((x) >= (unsigned long)-MAX_ERRNO)
+-
+-static inline void *ERR_PTR(long error)
+-{
+-	return (void *) error;
+-}
+-
+-static inline long PTR_ERR(const void *ptr)
+-{
+-	return (long) ptr;
+-}
+-
+-static inline int IS_ERR(const void *ptr)
+-{
+-	return IS_ERR_VALUE((unsigned long)ptr);
+-}
+-
+-static inline int IS_ERR_OR_NULL(const void *ptr)
+-{
+-	return !ptr || IS_ERR(ptr);
+-}
+-
+-/*
+- * This looks more complex than it should be. But we need to
+- * get the type for the ~ right in round_down (it needs to be
+- * as wide as the result!), and we want to evaluate the macro
+- * arguments just once each.
+- */
+-#define __round_mask(x, y) ((__typeof__(x))((y)-1))
+-#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
+-#define round_down(x, y) ((x) & ~__round_mask(x, y))
+-
+-/*
+- * printk
+- */
+-#define printk(fmt, args...) fprintf(stderr, fmt, ##args)
+-#define	KERN_CRIT	""
+-#define KERN_ERR	""
+-
+-/*
+- * kmalloc/kfree
+- */
+-#define kmalloc(x, y) malloc(x)
+-#define kzalloc(x, y) calloc(1, x)
+-#define kstrdup(x, y) strdup(x)
+-#define kfree(x) free(x)
+-#define vmalloc(x) malloc(x)
+-#define vfree(x) free(x)
+-
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-static inline void assert_trace(const char *assertion, const char *filename,
+-			      const char *func, unsigned line, long val)
+-{
+-	if (val)
+-		return;
+-	fprintf(stderr,
+-		"%s:%d: %s: Assertion `%s` failed, value %ld\n",
+-		filename, line, func, assertion, val);
+-#ifndef BTRFS_DISABLE_BACKTRACE
+-	print_trace();
+-#endif
+-	abort();
+-	exit(1);
+-}
+-#define	ASSERT(c) assert_trace(#c, __FILE__, __func__, __LINE__, (long)(c))
+-#else
+-#define ASSERT(c) assert(c)
+-#endif
+-
+-#define BUG_ON(c) bugon_trace(#c, __FILE__, __func__, __LINE__, (long)(c))
+-#define BUG() BUG_ON(1)
+-#define WARN_ON(c) warning_trace(#c, __FILE__, __func__, __LINE__, (long)(c))
+-
+-#define container_of(ptr, type, member) ({                      \
+-        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
+-	        (type *)( (char *)__mptr - offsetof(type,member) );})
+-#ifndef __bitwise
+-#ifdef __CHECKER__
+-#define __bitwise __bitwise__
+-#else
+-#define __bitwise
+-#endif /* __CHECKER__ */
+-#endif	/* __bitwise */
+-
+-/* Alignment check */
+-#define IS_ALIGNED(x, a)                (((x) & ((typeof(x))(a) - 1)) == 0)
+-
+-static inline int is_power_of_2(unsigned long n)
+-{
+-	return (n != 0 && ((n & (n - 1)) == 0));
+-}
+-
+-typedef u16 __bitwise __le16;
+-typedef u16 __bitwise __be16;
+-typedef u32 __bitwise __le32;
+-typedef u32 __bitwise __be32;
+-typedef u64 __bitwise __le64;
+-typedef u64 __bitwise __be64;
+-
+-/* Macros to generate set/get funcs for the struct fields
+- * assume there is a lefoo_to_cpu for every type, so lets make a simple
+- * one for u8:
+- */
+-#define le8_to_cpu(v) (v)
+-#define cpu_to_le8(v) (v)
+-#define __le8 u8
+-
+-#if __BYTE_ORDER == __BIG_ENDIAN
+-#define cpu_to_le64(x) ((__force __le64)(u64)(bswap_64(x)))
+-#define le64_to_cpu(x) ((__force u64)(__le64)(bswap_64(x)))
+-#define cpu_to_le32(x) ((__force __le32)(u32)(bswap_32(x)))
+-#define le32_to_cpu(x) ((__force u32)(__le32)(bswap_32(x)))
+-#define cpu_to_le16(x) ((__force __le16)(u16)(bswap_16(x)))
+-#define le16_to_cpu(x) ((__force u16)(__le16)(bswap_16(x)))
+-#else
+-#define cpu_to_le64(x) ((__force __le64)(u64)(x))
+-#define le64_to_cpu(x) ((__force u64)(__le64)(x))
+-#define cpu_to_le32(x) ((__force __le32)(u32)(x))
+-#define le32_to_cpu(x) ((__force u32)(__le32)(x))
+-#define cpu_to_le16(x) ((__force __le16)(u16)(x))
+-#define le16_to_cpu(x) ((__force u16)(__le16)(x))
+-#endif
+-
+-struct __una_u16 { __le16 x; } __attribute__((__packed__));
+-struct __una_u32 { __le32 x; } __attribute__((__packed__));
+-struct __una_u64 { __le64 x; } __attribute__((__packed__));
+-
+-#define get_unaligned_le8(p) (*((u8 *)(p)))
+-#define get_unaligned_8(p) (*((u8 *)(p)))
+-#define put_unaligned_le8(val,p) ((*((u8 *)(p))) = (val))
+-#define put_unaligned_8(val,p) ((*((u8 *)(p))) = (val))
+-#define get_unaligned_le16(p) le16_to_cpu(((const struct __una_u16 *)(p))->x)
+-#define get_unaligned_16(p) (((const struct __una_u16 *)(p))->x)
+-#define put_unaligned_le16(val,p) (((struct __una_u16 *)(p))->x = cpu_to_le16(val))
+-#define put_unaligned_16(val,p) (((struct __una_u16 *)(p))->x = (val))
+-#define get_unaligned_le32(p) le32_to_cpu(((const struct __una_u32 *)(p))->x)
+-#define get_unaligned_32(p) (((const struct __una_u32 *)(p))->x)
+-#define put_unaligned_le32(val,p) (((struct __una_u32 *)(p))->x = cpu_to_le32(val))
+-#define put_unaligned_32(val,p) (((struct __una_u32 *)(p))->x = (val))
+-#define get_unaligned_le64(p) le64_to_cpu(((const struct __una_u64 *)(p))->x)
+-#define get_unaligned_64(p) (((const struct __una_u64 *)(p))->x)
+-#define put_unaligned_le64(val,p) (((struct __una_u64 *)(p))->x = cpu_to_le64(val))
+-#define put_unaligned_64(val,p) (((struct __una_u64 *)(p))->x = (val))
+-
+-#ifndef true
+-#define true 1
+-#define false 0
+-#endif
+-
+-#ifndef noinline
+-#define noinline
+-#endif
+-
+-#endif
+diff --git a/radix-tree.c b/radix-tree.c
+deleted file mode 100644
+index f259ab5..0000000
+--- a/radix-tree.c
++++ /dev/null
+@@ -1,849 +0,0 @@
+-/*
+- * Copyright (C) 2007 Oracle.  All rights reserved.
+- *
+- * This program is free software; you can redistribute it and/or
+- * modify it under the terms of the GNU General Public
+- * License v2 as published by the Free Software Foundation.
+- *
+- * This program is distributed in the hope that it will be useful,
+- * but WITHOUT ANY WARRANTY; without even the implied warranty of
+- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+- * General Public License for more details.
+- *
+- * You should have received a copy of the GNU General Public
+- * License along with this program; if not, write to the
+- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+- * Boston, MA 021110-1307, USA.
+- */
+-
+-/*
+- * Copyright (C) 2001 Momchil Velikov
+- * Portions Copyright (C) 2001 Christoph Hellwig
+- * Copyright (C) 2005 SGI, Christoph Lameter <clameter@HIDDEN>
+- *
+- * This program is free software; you can redistribute it and/or
+- * modify it under the terms of the GNU General Public License as
+- * published by the Free Software Foundation; either version 2, or (at
+- * your option) any later version.
+- *
+- * This program is distributed in the hope that it will be useful, but
+- * WITHOUT ANY WARRANTY; without even the implied warranty of
+- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+- * General Public License for more details.
+- *
+- * You should have received a copy of the GNU General Public License
+- * along with this program; if not, write to the Free Software
+- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+- */
+-
+-#include "kerncompat.h"
+-#include "radix-tree.h"
+-#ifdef __KERNEL__
+-#define RADIX_TREE_MAP_SHIFT	(CONFIG_BASE_SMALL ? 4 : 6)
+-#else
+-#define RADIX_TREE_MAP_SHIFT	3	/* For more stressful testing */
+-#endif
+-
+-#define RADIX_TREE_MAP_SIZE	(1UL << RADIX_TREE_MAP_SHIFT)
+-#define RADIX_TREE_MAP_MASK	(RADIX_TREE_MAP_SIZE-1)
+-
+-#define RADIX_TREE_TAG_LONGS	\
+-	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
+-
+-struct radix_tree_node {
+-	unsigned int	count;
+-	void		*slots[RADIX_TREE_MAP_SIZE];
+-	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
+-};
+-
+-struct radix_tree_path {
+-	struct radix_tree_node *node;
+-	int offset;
+-};
+-
+-#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
+-#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
+-
+-static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
+-
+-/*
+- * Per-cpu pool of preloaded nodes
+- */
+-struct radix_tree_preload {
+-	int nr;
+-	struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
+-};
+-static struct radix_tree_preload radix_tree_preloads = { 0, };
+-
+-static int internal_nodes = 0;
+-/*
+- * This assumes that the caller has performed appropriate preallocation, and
+- * that the caller has pinned this thread of control to the current CPU.
+- */
+-static struct radix_tree_node *
+-radix_tree_node_alloc(struct radix_tree_root *root)
+-{
+-	struct radix_tree_node *ret;
+-	ret = malloc(sizeof(struct radix_tree_node));
+-	if (ret) {
+-		memset(ret, 0, sizeof(struct radix_tree_node));
+-		internal_nodes++;
+-	}
+-	return ret;
+-}
+-
+-static inline void
+-radix_tree_node_free(struct radix_tree_node *node)
+-{
+-	internal_nodes--;
+-	free(node);
+-}
+-
+-/*
+- * Load up this CPU's radix_tree_node buffer with sufficient objects to
+- * ensure that the addition of a single element in the tree cannot fail.  On
+- * success, return zero, with preemption disabled.  On error, return -ENOMEM
+- * with preemption not disabled.
+- */
+-int radix_tree_preload(gfp_t gfp_mask)
+-{
+-	struct radix_tree_preload *rtp;
+-	struct radix_tree_node *node;
+-	int ret = -ENOMEM;
+-
+-	preempt_disable();
+-	rtp = &__get_cpu_var(radix_tree_preloads);
+-	while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
+-		preempt_enable();
+-		node = radix_tree_node_alloc(NULL);
+-		if (node == NULL)
+-			goto out;
+-		preempt_disable();
+-		rtp = &__get_cpu_var(radix_tree_preloads);
+-		if (rtp->nr < ARRAY_SIZE(rtp->nodes))
+-			rtp->nodes[rtp->nr++] = node;
+-		else
+-			radix_tree_node_free(node);
+-	}
+-	ret = 0;
+-out:
+-	return ret;
+-}
+-
+-static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
+-		int offset)
+-{
+-	__set_bit(offset, node->tags[tag]);
+-}
+-
+-static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
+-		int offset)
+-{
+-	__clear_bit(offset, node->tags[tag]);
+-}
+-
+-static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
+-		int offset)
+-{
+-	return test_bit(offset, node->tags[tag]);
+-}
+-
+-static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
+-{
+-	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
+-}
+-
+-
+-static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
+-{
+-	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
+-}
+-
+-static inline void root_tag_clear_all(struct radix_tree_root *root)
+-{
+-	root->gfp_mask &= __GFP_BITS_MASK;
+-}
+-
+-static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
+-{
+-	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
+-}
+-
+-/*
+- * Returns 1 if any slot in the node has this tag set.
+- * Otherwise returns 0.
+- */
+-static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
+-{
+-	int idx;
+-	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
+-		if (node->tags[tag][idx])
+-			return 1;
+-	}
+-	return 0;
+-}
+-
+-/*
+- *	Return the maximum key which can be store into a
+- *	radix tree with height HEIGHT.
+- */
+-static inline unsigned long radix_tree_maxindex(unsigned int height)
+-{
+-	return height_to_maxindex[height];
+-}
+-
+-/*
+- *	Extend a radix tree so it can store key @index.
+- */
+-static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
+-{
+-	struct radix_tree_node *node;
+-	unsigned int height;
+-	int tag;
+-
+-	/* Figure out what the height should be.  */
+-	height = root->height + 1;
+-	while (index > radix_tree_maxindex(height))
+-		height++;
+-
+-	if (root->rnode == NULL) {
+-		root->height = height;
+-		goto out;
+-	}
+-
+-	do {
+-		if (!(node = radix_tree_node_alloc(root)))
+-			return -ENOMEM;
+-
+-		/* Increase the height.  */
+-		node->slots[0] = root->rnode;
+-
+-		/* Propagate the aggregated tag info into the new root */
+-		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
+-			if (root_tag_get(root, tag))
+-				tag_set(node, tag, 0);
+-		}
+-
+-		node->count = 1;
+-		root->rnode = node;
+-		root->height++;
+-	} while (height > root->height);
+-out:
+-	return 0;
+-}
+-
+-/**
+- *	radix_tree_insert    -    insert into a radix tree
+- *	@root:		radix tree root
+- *	@index:		index key
+- *	@item:		item to insert
+- *
+- *	Insert an item into the radix tree at position @index.
+- */
+-int radix_tree_insert(struct radix_tree_root *root,
+-			unsigned long index, void *item)
+-{
+-	struct radix_tree_node *node = NULL, *slot;
+-	unsigned int height, shift;
+-	int offset;
+-	int error;
+-
+-	/* Make sure the tree is high enough.  */
+-	if (index > radix_tree_maxindex(root->height)) {
+-		error = radix_tree_extend(root, index);
+-		if (error)
+-			return error;
+-	}
+-
+-	slot = root->rnode;
+-	height = root->height;
+-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+-
+-	offset = 0;			/* uninitialised var warning */
+-	while (height > 0) {
+-		if (slot == NULL) {
+-			/* Have to add a child node.  */
+-			if (!(slot = radix_tree_node_alloc(root)))
+-				return -ENOMEM;
+-			if (node) {
+-				node->slots[offset] = slot;
+-				node->count++;
+-			} else
+-				root->rnode = slot;
+-		}
+-
+-		/* Go a level down */
+-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+-		node = slot;
+-		slot = node->slots[offset];
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	}
+-
+-	if (slot != NULL)
+-		return -EEXIST;
+-
+-	if (node) {
+-		node->count++;
+-		node->slots[offset] = item;
+-		BUG_ON(tag_get(node, 0, offset));
+-		BUG_ON(tag_get(node, 1, offset));
+-	} else {
+-		root->rnode = item;
+-		BUG_ON(root_tag_get(root, 0));
+-		BUG_ON(root_tag_get(root, 1));
+-	}
+-
+-	return 0;
+-}
+-
+-static inline void **__lookup_slot(struct radix_tree_root *root,
+-				   unsigned long index)
+-{
+-	unsigned int height, shift;
+-	struct radix_tree_node **slot;
+-
+-	height = root->height;
+-
+-	if (index > radix_tree_maxindex(height))
+-		return NULL;
+-
+-	if (height == 0 && root->rnode)
+-		return (void *)&root->rnode;
+-
+-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+-	slot = &root->rnode;
+-
+-	while (height > 0) {
+-		if (*slot == NULL)
+-			return NULL;
+-
+-		slot = (struct radix_tree_node **)
+-			((*slot)->slots +
+-				((index >> shift) & RADIX_TREE_MAP_MASK));
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	}
+-
+-	return (void **)slot;
+-}
+-
+-/**
+- *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
+- *	@root:		radix tree root
+- *	@index:		index key
+- *
+- *	Lookup the slot corresponding to the position @index in the radix tree
+- *	@root. This is useful for update-if-exists operations.
+- */
+-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
+-{
+-	return __lookup_slot(root, index);
+-}
+-
+-/**
+- *	radix_tree_lookup    -    perform lookup operation on a radix tree
+- *	@root:		radix tree root
+- *	@index:		index key
+- *
+- *	Lookup the item at the position @index in the radix tree @root.
+- */
+-void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
+-{
+-	void **slot;
+-
+-	slot = __lookup_slot(root, index);
+-	return slot != NULL ? *slot : NULL;
+-}
+-
+-/**
+- *	radix_tree_tag_set - set a tag on a radix tree node
+- *	@root:		radix tree root
+- *	@index:		index key
+- *	@tag: 		tag index
+- *
+- *	Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
+- *	corresponding to @index in the radix tree.  From
+- *	the root all the way down to the leaf node.
+- *
+- *	Returns the address of the tagged item.   Setting a tag on a not-present
+- *	item is a bug.
+- */
+-void *radix_tree_tag_set(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag)
+-{
+-	unsigned int height, shift;
+-	struct radix_tree_node *slot;
+-
+-	height = root->height;
+-	BUG_ON(index > radix_tree_maxindex(height));
+-
+-	slot = root->rnode;
+-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+-
+-	while (height > 0) {
+-		int offset;
+-
+-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+-		if (!tag_get(slot, tag, offset))
+-			tag_set(slot, tag, offset);
+-		slot = slot->slots[offset];
+-		BUG_ON(slot == NULL);
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	}
+-
+-	/* set the root's tag bit */
+-	if (slot && !root_tag_get(root, tag))
+-		root_tag_set(root, tag);
+-
+-	return slot;
+-}
+-
+-/**
+- *	radix_tree_tag_clear - clear a tag on a radix tree node
+- *	@root:		radix tree root
+- *	@index:		index key
+- *	@tag: 		tag index
+- *
+- *	Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
+- *	corresponding to @index in the radix tree.  If
+- *	this causes the leaf node to have no tags set then clear the tag in the
+- *	next-to-leaf node, etc.
+- *
+- *	Returns the address of the tagged item on success, else NULL.  ie:
+- *	has the same return value and semantics as radix_tree_lookup().
+- */
+-void *radix_tree_tag_clear(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag)
+-{
+-	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+-	struct radix_tree_node *slot = NULL;
+-	unsigned int height, shift;
+-
+-	height = root->height;
+-	if (index > radix_tree_maxindex(height))
+-		goto out;
+-
+-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+-	pathp->node = NULL;
+-	slot = root->rnode;
+-
+-	while (height > 0) {
+-		int offset;
+-
+-		if (slot == NULL)
+-			goto out;
+-
+-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+-		pathp[1].offset = offset;
+-		pathp[1].node = slot;
+-		slot = slot->slots[offset];
+-		pathp++;
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	}
+-
+-	if (slot == NULL)
+-		goto out;
+-
+-	while (pathp->node) {
+-		if (!tag_get(pathp->node, tag, pathp->offset))
+-			goto out;
+-		tag_clear(pathp->node, tag, pathp->offset);
+-		if (any_tag_set(pathp->node, tag))
+-			goto out;
+-		pathp--;
+-	}
+-
+-	/* clear the root's tag bit */
+-	if (root_tag_get(root, tag))
+-		root_tag_clear(root, tag);
+-
+-out:
+-	return slot;
+-}
+-
+-#ifndef __KERNEL__	/* Only the test harness uses this at present */
+-/**
+- * radix_tree_tag_get - get a tag on a radix tree node
+- * @root:		radix tree root
+- * @index:		index key
+- * @tag: 		tag index (< RADIX_TREE_MAX_TAGS)
+- *
+- * Return values:
+- *
+- *  0: tag not present or not set
+- *  1: tag set
+- */
+-int radix_tree_tag_get(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag)
+-{
+-	unsigned int height, shift;
+-	struct radix_tree_node *slot;
+-	int saw_unset_tag = 0;
+-
+-	height = root->height;
+-	if (index > radix_tree_maxindex(height))
+-		return 0;
+-
+-	/* check the root's tag bit */
+-	if (!root_tag_get(root, tag))
+-		return 0;
+-
+-	if (height == 0)
+-		return 1;
+-
+-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+-	slot = root->rnode;
+-
+-	for ( ; ; ) {
+-		int offset;
+-
+-		if (slot == NULL)
+-			return 0;
+-
+-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+-
+-		/*
+-		 * This is just a debug check.  Later, we can bale as soon as
+-		 * we see an unset tag.
+-		 */
+-		if (!tag_get(slot, tag, offset))
+-			saw_unset_tag = 1;
+-		if (height == 1) {
+-			int ret = tag_get(slot, tag, offset);
+-
+-			BUG_ON(ret && saw_unset_tag);
+-			return !!ret;
+-		}
+-		slot = slot->slots[offset];
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	}
+-}
+-#endif
+-
+-static unsigned int
+-__lookup(struct radix_tree_root *root, void **results, unsigned long index,
+-	unsigned int max_items, unsigned long *next_index)
+-{
+-	unsigned int nr_found = 0;
+-	unsigned int shift, height;
+-	struct radix_tree_node *slot;
+-	unsigned long i;
+-
+-	height = root->height;
+-	if (height == 0) {
+-		if (root->rnode && index == 0)
+-			results[nr_found++] = root->rnode;
+-		goto out;
+-	}
+-
+-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+-	slot = root->rnode;
+-
+-	for ( ; height > 1; height--) {
+-
+-		for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
+-				i < RADIX_TREE_MAP_SIZE; i++) {
+-			if (slot->slots[i] != NULL)
+-				break;
+-			index &= ~((1UL << shift) - 1);
+-			index += 1UL << shift;
+-			if (index == 0)
+-				goto out;	/* 32-bit wraparound */
+-		}
+-		if (i == RADIX_TREE_MAP_SIZE)
+-			goto out;
+-
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		slot = slot->slots[i];
+-	}
+-
+-	/* Bottom level: grab some items */
+-	for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
+-		index++;
+-		if (slot->slots[i]) {
+-			results[nr_found++] = slot->slots[i];
+-			if (nr_found == max_items)
+-				goto out;
+-		}
+-	}
+-out:
+-	*next_index = index;
+-	return nr_found;
+-}
+-
+-/**
+- *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
+- *	@root:		radix tree root
+- *	@results:	where the results of the lookup are placed
+- *	@first_index:	start the lookup from this key
+- *	@max_items:	place up to this many items at *results
+- *
+- *	Performs an index-ascending scan of the tree for present items.  Places
+- *	them at *@results and returns the number of items which were placed at
+- *	*@results.
+- *
+- *	The implementation is naive.
+- */
+-unsigned int
+-radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
+-			unsigned long first_index, unsigned int max_items)
+-{
+-	const unsigned long max_index = radix_tree_maxindex(root->height);
+-	unsigned long cur_index = first_index;
+-	unsigned int ret = 0;
+-
+-	while (ret < max_items) {
+-		unsigned int nr_found;
+-		unsigned long next_index;	/* Index of next search */
+-
+-		if (cur_index > max_index)
+-			break;
+-		nr_found = __lookup(root, results + ret, cur_index,
+-					max_items - ret, &next_index);
+-		ret += nr_found;
+-		if (next_index == 0)
+-			break;
+-		cur_index = next_index;
+-	}
+-	return ret;
+-}
+-
+-/*
+- * FIXME: the two tag_get()s here should use find_next_bit() instead of
+- * open-coding the search.
+- */
+-static unsigned int
+-__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
+-	unsigned int max_items, unsigned long *next_index, unsigned int tag)
+-{
+-	unsigned int nr_found = 0;
+-	unsigned int shift;
+-	unsigned int height = root->height;
+-	struct radix_tree_node *slot;
+-
+-	if (height == 0) {
+-		if (root->rnode && index == 0)
+-			results[nr_found++] = root->rnode;
+-		goto out;
+-	}
+-
+-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+-	slot = root->rnode;
+-
+-	do {
+-		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
+-
+-		for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
+-			if (tag_get(slot, tag, i)) {
+-				BUG_ON(slot->slots[i] == NULL);
+-				break;
+-			}
+-			index &= ~((1UL << shift) - 1);
+-			index += 1UL << shift;
+-			if (index == 0)
+-				goto out;	/* 32-bit wraparound */
+-		}
+-		if (i == RADIX_TREE_MAP_SIZE)
+-			goto out;
+-		height--;
+-		if (height == 0) {	/* Bottom level: grab some items */
+-			unsigned long j = index & RADIX_TREE_MAP_MASK;
+-
+-			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
+-				index++;
+-				if (tag_get(slot, tag, j)) {
+-					BUG_ON(slot->slots[j] == NULL);
+-					results[nr_found++] = slot->slots[j];
+-					if (nr_found == max_items)
+-						goto out;
+-				}
+-			}
+-		}
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		slot = slot->slots[i];
+-	} while (height > 0);
+-out:
+-	*next_index = index;
+-	return nr_found;
+-}
+-
+-/**
+- *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
+- *	                             based on a tag
+- *	@root:		radix tree root
+- *	@results:	where the results of the lookup are placed
+- *	@first_index:	start the lookup from this key
+- *	@max_items:	place up to this many items at *results
+- *	@tag:		the tag index (< RADIX_TREE_MAX_TAGS)
+- *
+- *	Performs an index-ascending scan of the tree for present items which
+- *	have the tag indexed by @tag set.  Places the items at *@results and
+- *	returns the number of items which were placed at *@results.
+- */
+-unsigned int
+-radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
+-		unsigned long first_index, unsigned int max_items,
+-		unsigned int tag)
+-{
+-	const unsigned long max_index = radix_tree_maxindex(root->height);
+-	unsigned long cur_index = first_index;
+-	unsigned int ret = 0;
+-
+-	/* check the root's tag bit */
+-	if (!root_tag_get(root, tag))
+-		return 0;
+-
+-	while (ret < max_items) {
+-		unsigned int nr_found;
+-		unsigned long next_index;	/* Index of next search */
+-
+-		if (cur_index > max_index)
+-			break;
+-		nr_found = __lookup_tag(root, results + ret, cur_index,
+-					max_items - ret, &next_index, tag);
+-		ret += nr_found;
+-		if (next_index == 0)
+-			break;
+-		cur_index = next_index;
+-	}
+-	return ret;
+-}
+-
+-/**
+- *	radix_tree_shrink    -    shrink height of a radix tree to minimal
+- *	@root		radix tree root
+- */
+-static inline void radix_tree_shrink(struct radix_tree_root *root)
+-{
+-	/* try to shrink tree height */
+-	while (root->height > 0 &&
+-			root->rnode->count == 1 &&
+-			root->rnode->slots[0]) {
+-		struct radix_tree_node *to_free = root->rnode;
+-
+-		root->rnode = to_free->slots[0];
+-		root->height--;
+-		/* must only free zeroed nodes into the slab */
+-		tag_clear(to_free, 0, 0);
+-		tag_clear(to_free, 1, 0);
+-		to_free->slots[0] = NULL;
+-		to_free->count = 0;
+-		radix_tree_node_free(to_free);
+-	}
+-}
+-
+-/**
+- *	radix_tree_delete    -    delete an item from a radix tree
+- *	@root:		radix tree root
+- *	@index:		index key
+- *
+- *	Remove the item at @index from the radix tree rooted at @root.
+- *
+- *	Returns the address of the deleted item, or NULL if it was not present.
+- */
+-void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
+-{
+-	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+-	struct radix_tree_node *slot = NULL;
+-	unsigned int height, shift;
+-	int tag;
+-	int offset;
+-
+-	height = root->height;
+-	if (index > radix_tree_maxindex(height))
+-		goto out;
+-
+-	slot = root->rnode;
+-	if (height == 0 && root->rnode) {
+-		root_tag_clear_all(root);
+-		root->rnode = NULL;
+-		goto out;
+-	}
+-
+-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+-	pathp->node = NULL;
+-
+-	do {
+-		if (slot == NULL)
+-			goto out;
+-
+-		pathp++;
+-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+-		pathp->offset = offset;
+-		pathp->node = slot;
+-		slot = slot->slots[offset];
+-		shift -= RADIX_TREE_MAP_SHIFT;
+-		height--;
+-	} while (height > 0);
+-
+-	if (slot == NULL)
+-		goto out;
+-
+-	/*
+-	 * Clear all tags associated with the just-deleted item
+-	 */
+-	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
+-		if (tag_get(pathp->node, tag, pathp->offset))
+-			radix_tree_tag_clear(root, index, tag);
+-	}
+-
+-	/* Now free the nodes we do not need anymore */
+-	while (pathp->node) {
+-		pathp->node->slots[pathp->offset] = NULL;
+-		pathp->node->count--;
+-
+-		if (pathp->node->count) {
+-			if (pathp->node == root->rnode)
+-				radix_tree_shrink(root);
+-			goto out;
+-		}
+-
+-		/* Node with zero slots in use so free it */
+-		radix_tree_node_free(pathp->node);
+-
+-		pathp--;
+-	}
+-	root_tag_clear_all(root);
+-	root->height = 0;
+-	root->rnode = NULL;
+-
+-out:
+-	return slot;
+-}
+-
+-/**
+- *	radix_tree_tagged - test whether any items in the tree are tagged
+- *	@root:		radix tree root
+- *	@tag:		tag to test
+- */
+-int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
+-{
+-	return root_tag_get(root, tag);
+-}
+-
+-static unsigned long __maxindex(unsigned int height)
+-{
+-	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
+-	unsigned long index = ~0UL;
+-
+-	if (tmp < RADIX_TREE_INDEX_BITS)
+-		index = (index >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+-	return index;
+-}
+-
+-static void radix_tree_init_maxindex(void)
+-{
+-	unsigned int i;
+-
+-	for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
+-		height_to_maxindex[i] = __maxindex(i);
+-}
+-
+-void radix_tree_init(void)
+-{
+-	radix_tree_init_maxindex();
+-}
+diff --git a/radix-tree.h b/radix-tree.h
+deleted file mode 100644
+index bf96d83..0000000
+--- a/radix-tree.h
++++ /dev/null
+@@ -1,97 +0,0 @@
+-/*
+- * Copyright (C) 2007 Oracle.  All rights reserved.
+- *
+- * This program is free software; you can redistribute it and/or
+- * modify it under the terms of the GNU General Public
+- * License v2 as published by the Free Software Foundation.
+- *
+- * This program is distributed in the hope that it will be useful,
+- * but WITHOUT ANY WARRANTY; without even the implied warranty of
+- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+- * General Public License for more details.
+- *
+- * You should have received a copy of the GNU General Public
+- * License along with this program; if not, write to the
+- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+- * Boston, MA 021110-1307, USA.
+- */
+-
+-/*
+- * Copyright (C) 2001 Momchil Velikov
+- * Portions Copyright (C) 2001 Christoph Hellwig
+- *
+- * This program is free software; you can redistribute it and/or
+- * modify it under the terms of the GNU General Public License as
+- * published by the Free Software Foundation; either version 2, or (at
+- * your option) any later version.
+- * 
+- * This program is distributed in the hope that it will be useful, but
+- * WITHOUT ANY WARRANTY; without even the implied warranty of
+- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+- * General Public License for more details.
+- * 
+- * You should have received a copy of the GNU General Public License
+- * along with this program; if not, write to the Free Software
+- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+- */
+-#ifndef _LINUX_RADIX_TREE_H
+-#define _LINUX_RADIX_TREE_H
+-
+-#if BTRFS_FLAT_INCLUDES
+-#include "kerncompat.h"
+-#else
+-#include <btrfs/kerncompat.h>
+-#endif /* BTRFS_FLAT_INCLUDES */
+-
+-#define RADIX_TREE_MAX_TAGS 2
+-
+-/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
+-struct radix_tree_root {
+-	unsigned int		height;
+-	gfp_t			gfp_mask;
+-	struct radix_tree_node	*rnode;
+-};
+-
+-#define RADIX_TREE_INIT(mask)	{					\
+-	.height = 0,							\
+-	.gfp_mask = (mask),						\
+-	.rnode = NULL,							\
+-}
+-
+-#define RADIX_TREE(name, mask) \
+-	struct radix_tree_root name = RADIX_TREE_INIT(mask)
+-
+-#define INIT_RADIX_TREE(root, mask)					\
+-do {									\
+-	(root)->height = 0;						\
+-	(root)->gfp_mask = (mask);					\
+-	(root)->rnode = NULL;						\
+-} while (0)
+-
+-int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
+-void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
+-void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+-void *radix_tree_delete(struct radix_tree_root *, unsigned long);
+-unsigned int
+-radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
+-			unsigned long first_index, unsigned int max_items);
+-int radix_tree_preload(gfp_t gfp_mask);
+-void radix_tree_init(void);
+-void *radix_tree_tag_set(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag);
+-void *radix_tree_tag_clear(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag);
+-int radix_tree_tag_get(struct radix_tree_root *root,
+-			unsigned long index, unsigned int tag);
+-unsigned int
+-radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
+-		unsigned long first_index, unsigned int max_items,
+-		unsigned int tag);
+-int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
+-
+-static inline void radix_tree_preload_end(void)
+-{
+-	preempt_enable();
+-}
+-
+-#endif /* _LINUX_RADIX_TREE_H */

base-commit: 12a6dd40a7b88454cc8a8c930c22681fcee5b1ea
-- 
2.49.0

Last modified: Tue, 15 Apr 2025 19:00:09 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.