rust/kernel/gpu/buddy.rs - third_party/linux - Git at Google

 // SPDX-License-Identifier: GPL-2.0

 //! GPU buddy allocator bindings.
 //!
 //! C header: [`include/linux/gpu_buddy.h`](srctree/include/linux/gpu_buddy.h)
 //!
 //! This module provides Rust abstractions over the Linux kernel's GPU buddy
 //! allocator, which implements a binary buddy memory allocator.
 //!
 //! The buddy allocator manages a contiguous address space and allocates blocks
 //! in power-of-two sizes, useful for GPU physical memory management.
 //!
 //! # Examples
 //!
 //! Create a buddy allocator and perform a basic range allocation:
 //!
 //! ```
 //! use kernel::{
 //!     gpu::buddy::{
 //!         GpuBuddy,
 //!         GpuBuddyAllocFlags,
 //!         GpuBuddyAllocMode,
 //!         GpuBuddyParams, //
 //!     },
 //!     prelude::*,
 //!     ptr::Alignment,
 //!     sizes::*, //
 //! };
 //!
 //! // Create a 1GB buddy allocator with 4KB minimum chunk size.
 //! let buddy = GpuBuddy::new(GpuBuddyParams {
 //!     base_offset: 0,
 //!     size: SZ_1G as u64,
 //!     chunk_size: Alignment::new::<SZ_4K>(),
 //! })?;
 //!
 //! assert_eq!(buddy.size(), SZ_1G as u64);
 //! assert_eq!(buddy.chunk_size(), Alignment::new::<SZ_4K>());
 //! let initial_free = buddy.avail();
 //!
 //! // Allocate 16MB. Block lands at the top of the address range.
 //! let allocated = KBox::pin_init(
 //!     buddy.alloc_blocks(
 //!         GpuBuddyAllocMode::Simple,
 //!         SZ_16M as u64,
 //!         Alignment::new::<SZ_16M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
 //!
 //! let block = allocated.iter().next().expect("expected one block");
 //! assert_eq!(block.offset(), (SZ_1G - SZ_16M) as u64);
 //! assert_eq!(block.order(), 12); // 2^12 pages = 16MB
 //! assert_eq!(block.size(), SZ_16M as u64);
 //! assert_eq!(allocated.iter().count(), 1);
 //!
 //! // Dropping the allocation returns the range to the buddy allocator.
 //! drop(allocated);
 //! assert_eq!(buddy.avail(), initial_free);
 //! # Ok::<(), Error>(())
 //! ```
 //!
 //! Top-down allocation allocates from the highest addresses:
 //!
 //! ```
 //! # use kernel::{
 //! #     gpu::buddy::{GpuBuddy, GpuBuddyAllocMode, GpuBuddyAllocFlags, GpuBuddyParams},
 //! #     prelude::*,
 //! #     ptr::Alignment,
 //! #     sizes::*, //
 //! # };
 //! # let buddy = GpuBuddy::new(GpuBuddyParams {
 //! #     base_offset: 0,
 //! #     size: SZ_1G as u64,
 //! #     chunk_size: Alignment::new::<SZ_4K>(),
 //! # })?;
 //! # let initial_free = buddy.avail();
 //! let topdown = KBox::pin_init(
 //!     buddy.alloc_blocks(
 //!         GpuBuddyAllocMode::TopDown,
 //!         SZ_16M as u64,
 //!         Alignment::new::<SZ_16M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
 //!
 //! let block = topdown.iter().next().expect("expected one block");
 //! assert_eq!(block.offset(), (SZ_1G - SZ_16M) as u64);
 //! assert_eq!(block.order(), 12);
 //! assert_eq!(block.size(), SZ_16M as u64);
 //!
 //! // Dropping the allocation returns the range to the buddy allocator.
 //! drop(topdown);
 //! assert_eq!(buddy.avail(), initial_free);
 //! # Ok::<(), Error>(())
 //! ```
 //!
 //! Non-contiguous allocation can fill fragmented memory by returning multiple
 //! blocks:
 //!
 //! ```
 //! # use kernel::{
 //! #     gpu::buddy::{
 //! #         GpuBuddy, GpuBuddyAllocFlags, GpuBuddyAllocMode, GpuBuddyParams,
 //! #     },
 //! #     prelude::*,
 //! #     ptr::Alignment,
 //! #     sizes::*, //
 //! # };
 //! # let buddy = GpuBuddy::new(GpuBuddyParams {
 //! #     base_offset: 0,
 //! #     size: SZ_1G as u64,
 //! #     chunk_size: Alignment::new::<SZ_4K>(),
 //! # })?;
 //! # let initial_free = buddy.avail();
 //! // Create fragmentation by allocating 4MB blocks at [0,4M) and [8M,12M).
 //! let frag1 = KBox::pin_init(
 //!     buddy.alloc_blocks(
 //!         GpuBuddyAllocMode::Range(0..SZ_4M as u64),
 //!         SZ_4M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //! assert_eq!(buddy.avail(), initial_free - SZ_4M as u64);
 //!
 //! let frag2 = KBox::pin_init(
 //!     buddy.alloc_blocks(
 //!         GpuBuddyAllocMode::Range(SZ_8M as u64..(SZ_8M + SZ_4M) as u64),
 //!         SZ_4M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //! assert_eq!(buddy.avail(), initial_free - SZ_8M as u64);
 //!
 //! // Allocate 8MB, this returns 2 blocks from the holes.
 //! let fragmented = KBox::pin_init(
 //!     buddy.alloc_blocks(
 //!         GpuBuddyAllocMode::Range(0..SZ_16M as u64),
 //!         SZ_8M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
 //!
 //! let (mut count, mut total) = (0u32, 0u64);
 //! for block in fragmented.iter() {
 //!     assert_eq!(block.size(), SZ_4M as u64);
 //!     total += block.size();
 //!     count += 1;
 //! }
 //! assert_eq!(total, SZ_8M as u64);
 //! assert_eq!(count, 2);
 //! # Ok::<(), Error>(())
 //! ```
 //!
 //! Contiguous allocation fails when only fragmented space is available:
 //!
 //! ```
 //! # use kernel::{
 //! #     gpu::buddy::{
 //! #         GpuBuddy, GpuBuddyAllocFlag, GpuBuddyAllocFlags, GpuBuddyAllocMode, GpuBuddyParams,
 //! #     },
 //! #     prelude::*,
 //! #     ptr::Alignment,
 //! #     sizes::*, //
 //! # };
 //! // Create a small 16MB buddy allocator with fragmented memory.
 //! let small = GpuBuddy::new(GpuBuddyParams {
 //!     base_offset: 0,
 //!     size: SZ_16M as u64,
 //!     chunk_size: Alignment::new::<SZ_4K>(),
 //! })?;
 //!
 //! let _hole1 = KBox::pin_init(
 //!     small.alloc_blocks(
 //!         GpuBuddyAllocMode::Range(0..SZ_4M as u64),
 //!         SZ_4M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //!
 //! let _hole2 = KBox::pin_init(
 //!     small.alloc_blocks(
 //!         GpuBuddyAllocMode::Range(SZ_8M as u64..(SZ_8M + SZ_4M) as u64),
 //!         SZ_4M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlags::default(),
 //!     ),
 //!     GFP_KERNEL,
 //! )?;
 //!
 //! // 8MB contiguous should fail, only two non-contiguous 4MB holes exist.
 //! let result = KBox::pin_init(
 //!     small.alloc_blocks(
 //!         GpuBuddyAllocMode::Simple,
 //!         SZ_8M as u64,
 //!         Alignment::new::<SZ_4M>(),
 //!         GpuBuddyAllocFlag::Contiguous,
 //!     ),
 //!     GFP_KERNEL,
 //! );
 //! assert!(result.is_err());
 //! # Ok::<(), Error>(())
 //! ```

 use core::ops::Range;

 use crate::{
     bindings,
     clist_create,
     error::to_result,
     interop::list::CListHead,
     new_mutex,
     prelude::*,
     ptr::Alignment,
     sync::{
         lock::mutex::MutexGuard,
         Arc,
         Mutex, //
     },
     types::Opaque, //
 };

 /// Allocation mode for the GPU buddy allocator.
 ///
 /// The mode determines the primary allocation strategy. Modes are mutually
 /// exclusive: an allocation is either simple, range-constrained, or top-down.
 ///
 /// Orthogonal modifier flags (e.g., contiguous, clear) are specified separately
 /// via [`GpuBuddyAllocFlags`].
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub enum GpuBuddyAllocMode {
     /// Simple allocation without constraints.
     Simple,
     /// Range-based allocation within the given address range.
     Range(Range<u64>),
     /// Allocate from top of address space downward.
     TopDown,
 }

 impl GpuBuddyAllocMode {
     /// Returns the C flags corresponding to the allocation mode.
     fn as_flags(&self) -> usize {
         match self {
             Self::Simple => 0,
             Self::Range(_) => bindings::GPU_BUDDY_RANGE_ALLOCATION,
             Self::TopDown => bindings::GPU_BUDDY_TOPDOWN_ALLOCATION,
         }
     }

     /// Extracts the range start/end, defaulting to `(0, 0)` for non-range modes.
     fn range(&self) -> (u64, u64) {
         match self {
             Self::Range(range) => (range.start, range.end),
             _ => (0, 0),
         }
     }
 }

 crate::impl_flags!(
     /// Modifier flags for GPU buddy allocation.
     ///
     /// These flags can be combined with any [`GpuBuddyAllocMode`] to control
     /// additional allocation behavior.
     #[derive(Clone, Copy, Default, PartialEq, Eq)]
     pub struct GpuBuddyAllocFlags(usize);

     /// Individual modifier flag for GPU buddy allocation.
     #[derive(Clone, Copy, PartialEq, Eq)]
     pub enum GpuBuddyAllocFlag {
         /// Allocate physically contiguous blocks.
         Contiguous = bindings::GPU_BUDDY_CONTIGUOUS_ALLOCATION,

         /// Request allocation from cleared (zeroed) memory.
         Clear = bindings::GPU_BUDDY_CLEAR_ALLOCATION,

         /// Disable trimming of partially used blocks.
         TrimDisable = bindings::GPU_BUDDY_TRIM_DISABLE,
     }
 );

 /// Parameters for creating a GPU buddy allocator.
 pub struct GpuBuddyParams {
     /// Base offset (in bytes) where the managed memory region starts.
     /// Allocations will be offset by this value.
     pub base_offset: u64,
     /// Total size (in bytes) of the address space managed by the allocator.
     pub size: u64,
     /// Minimum allocation unit / chunk size; must be >= 4KB.
     pub chunk_size: Alignment,
 }

 /// Inner structure holding the actual buddy allocator.
 ///
 /// # Synchronization
 ///
 /// The C `gpu_buddy` API requires synchronization (see `include/linux/gpu_buddy.h`).
 /// Internal locking ensures all allocator and free operations are properly
 /// synchronized, preventing races between concurrent allocations and the
 /// freeing that occurs when [`AllocatedBlocks`] is dropped.
 ///
 /// # Invariants
 ///
 /// The inner [`Opaque`] contains an initialized buddy allocator.
 #[pin_data(PinnedDrop)]
 struct GpuBuddyInner {
     #[pin]
     inner: Opaque<bindings::gpu_buddy>,

     // TODO: Replace `Mutex<()>` with `Mutex<Opaque<..>>` once `Mutex::new()`
     // accepts `impl PinInit<T>`.
     #[pin]
     lock: Mutex<()>,
     /// Cached creation parameters (do not change after init).
     params: GpuBuddyParams,
 }

 impl GpuBuddyInner {
     /// Create a pin-initializer for the buddy allocator.
     fn new(params: GpuBuddyParams) -> impl PinInit<Self, Error> {
         let size = params.size;
         let chunk_size = params.chunk_size;

         // INVARIANT: `gpu_buddy_init` returns 0 on success, at which point the
         // `gpu_buddy` structure is initialized and ready for use with all
         // `gpu_buddy_*` APIs. `try_pin_init!` only completes if all fields succeed,
         // so the invariant holds when construction finishes.
         try_pin_init!(Self {
             inner <- Opaque::try_ffi_init(|ptr| {
                 // SAFETY: `ptr` points to valid uninitialized memory from the pin-init
                 // infrastructure. `gpu_buddy_init` will initialize the structure.
                 to_result(unsafe {
                     bindings::gpu_buddy_init(ptr, size, chunk_size.as_usize() as u64)
                 })
             }),
             lock <- new_mutex!(()),
             params,
         })
     }

     /// Lock the mutex and return a guard for accessing the allocator.
     fn lock(&self) -> GpuBuddyGuard<'_> {
         GpuBuddyGuard {
             inner: self,
             _guard: self.lock.lock(),
         }
     }
 }

 #[pinned_drop]
 impl PinnedDrop for GpuBuddyInner {
     fn drop(self: Pin<&mut Self>) {
         let guard = self.lock();

         // SAFETY: Per the type invariant, `inner` contains an initialized
         // allocator. `guard` provides exclusive access.
         unsafe { bindings::gpu_buddy_fini(guard.as_raw()) };
     }
 }

 // SAFETY: `GpuBuddyInner` can be sent between threads.
 unsafe impl Send for GpuBuddyInner {}

 // SAFETY: `GpuBuddyInner` is `Sync` because `GpuBuddyInner::lock`
 // serializes all access to the C allocator, preventing data races.
 unsafe impl Sync for GpuBuddyInner {}

 /// Guard that proves the lock is held, enabling access to the allocator.
 ///
 /// The `_guard` holds the lock for the duration of this guard's lifetime.
 struct GpuBuddyGuard<'a> {
     inner: &'a GpuBuddyInner,
     _guard: MutexGuard<'a, ()>,
 }

 impl GpuBuddyGuard<'_> {
     /// Get a raw pointer to the underlying C `gpu_buddy` structure.
     fn as_raw(&self) -> *mut bindings::gpu_buddy {
         self.inner.inner.get()
     }
 }

 /// GPU buddy allocator instance.
 ///
 /// This structure wraps the C `gpu_buddy` allocator using reference counting.
 /// The allocator is automatically cleaned up when all references are dropped.
 ///
 /// Refer to the module-level documentation for usage examples.
 pub struct GpuBuddy(Arc<GpuBuddyInner>);

 impl GpuBuddy {
     /// Create a new buddy allocator.
     ///
     /// The allocator manages a contiguous address space of the given size, with the
     /// specified minimum allocation unit (chunk_size must be at least 4KB).
     pub fn new(params: GpuBuddyParams) -> Result<Self> {
         Arc::pin_init(GpuBuddyInner::new(params), GFP_KERNEL).map(Self)
     }

     /// Get the base offset for allocations.
     pub fn base_offset(&self) -> u64 {
         self.0.params.base_offset
     }

     /// Get the chunk size (minimum allocation unit).
     pub fn chunk_size(&self) -> Alignment {
         self.0.params.chunk_size
     }

     /// Get the total managed size.
     pub fn size(&self) -> u64 {
         self.0.params.size
     }

     /// Get the available (free) memory in bytes.
     pub fn avail(&self) -> u64 {
         let guard = self.0.lock();

         // SAFETY: Per the type invariant, `inner` contains an initialized allocator.
         // `guard` provides exclusive access.
         unsafe { (*guard.as_raw()).avail }
     }

     /// Allocate blocks from the buddy allocator.
     ///
     /// Returns a pin-initializer for [`AllocatedBlocks`].
     pub fn alloc_blocks(
         &self,
         mode: GpuBuddyAllocMode,
         size: u64,
         min_block_size: Alignment,
         flags: impl Into<GpuBuddyAllocFlags>,
     ) -> impl PinInit<AllocatedBlocks, Error> {
         let buddy_arc = Arc::clone(&self.0);
         let (start, end) = mode.range();
         let mode_flags = mode.as_flags();
         let modifier_flags = flags.into();

         // Create pin-initializer that initializes list and allocates blocks.
         try_pin_init!(AllocatedBlocks {
             buddy: buddy_arc,
             list <- CListHead::new(),
             _: {
                 // Reject zero-sized or inverted ranges.
                 if let GpuBuddyAllocMode::Range(range) = &mode {
                     if range.is_empty() {
                         Err::<(), Error>(EINVAL)?;
                     }
                 }

                 // Lock while allocating to serialize with concurrent frees.
                 let guard = buddy.lock();

                 // SAFETY: Per the type invariant, `inner` contains an initialized
                 // allocator. `guard` provides exclusive access.
                 to_result(unsafe {
                     bindings::gpu_buddy_alloc_blocks(
                         guard.as_raw(),
                         start,
                         end,
                         size,
                         min_block_size.as_usize() as u64,
                         list.as_raw(),
                         mode_flags | usize::from(modifier_flags),
                     )
                 })?
             }
         })
     }
 }

 /// Allocated blocks from the buddy allocator with automatic cleanup.
 ///
 /// This structure owns a list of allocated blocks and ensures they are
 /// automatically freed when dropped. Use `iter()` to iterate over all
 /// allocated blocks.
 ///
 /// # Invariants
 ///
 /// - `list` is an initialized, valid list head containing allocated blocks.
 #[pin_data(PinnedDrop)]
 pub struct AllocatedBlocks {
     #[pin]
     list: CListHead,
     buddy: Arc<GpuBuddyInner>,
 }

 impl AllocatedBlocks {
     /// Check if the block list is empty.
     pub fn is_empty(&self) -> bool {
         // An empty list head points to itself.
         !self.list.is_linked()
     }

     /// Iterate over allocated blocks.
     ///
     /// Returns an iterator yielding [`AllocatedBlock`] values. Each [`AllocatedBlock`]
     /// borrows `self` and is only valid for the duration of that borrow.
     pub fn iter(&self) -> impl Iterator<Item = AllocatedBlock<'_>> + '_ {
         let head = self.list.as_raw();
         // SAFETY: Per the type invariant, `list` is an initialized sentinel `list_head`
         // and is not concurrently modified (we hold a `&self` borrow). The list contains
         // `gpu_buddy_block` items linked via `__bindgen_anon_1.link`. `Block` is
         // `#[repr(transparent)]` over `gpu_buddy_block`.
         let clist = unsafe {
             clist_create!(
                 head,
                 Block,
                 bindings::gpu_buddy_block,
                 __bindgen_anon_1.link
             )
         };

         clist
             .iter()
             .map(|this| AllocatedBlock { this, blocks: self })
     }
 }

 #[pinned_drop]
 impl PinnedDrop for AllocatedBlocks {
     fn drop(self: Pin<&mut Self>) {
         let guard = self.buddy.lock();

         // SAFETY:
         // - list is valid per the type's invariants.
         // - guard provides exclusive access to the allocator.
         unsafe {
             bindings::gpu_buddy_free_list(guard.as_raw(), self.list.as_raw(), 0);
         }
     }
 }

 /// A GPU buddy block.
 ///
 /// Transparent wrapper over C `gpu_buddy_block` structure. This type is returned
 /// as references during iteration over [`AllocatedBlocks`].
 ///
 /// # Invariants
 ///
 /// The inner [`Opaque`] contains a valid, allocated `gpu_buddy_block`.
 #[repr(transparent)]
 struct Block(Opaque<bindings::gpu_buddy_block>);

 impl Block {
     /// Get a raw pointer to the underlying C block.
     fn as_raw(&self) -> *mut bindings::gpu_buddy_block {
         self.0.get()
     }

     /// Get the block's raw offset in the buddy address space (without base offset).
     fn offset(&self) -> u64 {
         // SAFETY: `self.as_raw()` is valid per the type's invariants.
         unsafe { bindings::gpu_buddy_block_offset(self.as_raw()) }
     }

     /// Get the block order.
     fn order(&self) -> u32 {
         // SAFETY: `self.as_raw()` is valid per the type's invariants.
         unsafe { bindings::gpu_buddy_block_order(self.as_raw()) }
     }
 }

 // SAFETY: `Block` is a wrapper around `gpu_buddy_block` which can be
 // sent across threads safely.
 unsafe impl Send for Block {}

 // SAFETY: `Block` is only accessed through shared references after
 // allocation, and thus safe to access concurrently across threads.
 unsafe impl Sync for Block {}

 /// A buddy block paired with its owning [`AllocatedBlocks`] context.
 ///
 /// Unlike a raw block, which only knows its offset within the buddy address
 /// space, an [`AllocatedBlock`] also has access to the allocator's `base_offset`
 /// and `chunk_size`, enabling it to compute absolute offsets and byte sizes.
 ///
 /// Returned by [`AllocatedBlocks::iter()`].
 pub struct AllocatedBlock<'a> {
     this: &'a Block,
     blocks: &'a AllocatedBlocks,
 }

 impl AllocatedBlock<'_> {
     /// Get the block's offset in the address space.
     ///
     /// Returns the absolute offset including the allocator's base offset.
     /// This is the actual address to use for accessing the allocated memory.
     pub fn offset(&self) -> u64 {
         self.blocks.buddy.params.base_offset + self.this.offset()
     }

     /// Get the block order (size = chunk_size << order).
     pub fn order(&self) -> u32 {
         self.this.order()
     }

     /// Get the block's size in bytes.
     pub fn size(&self) -> u64 {
         (self.blocks.buddy.params.chunk_size.as_usize() as u64) << self.this.order()
     }
 }
	// SPDX-License-Identifier: GPL-2.0

	//! GPU buddy allocator bindings.
	//!
	//! C header: [`include/linux/gpu_buddy.h`](srctree/include/linux/gpu_buddy.h)
	//!
	//! This module provides Rust abstractions over the Linux kernel's GPU buddy
	//! allocator, which implements a binary buddy memory allocator.
	//!
	//! The buddy allocator manages a contiguous address space and allocates blocks
	//! in power-of-two sizes, useful for GPU physical memory management.
	//!
	//! # Examples
	//!
	//! Create a buddy allocator and perform a basic range allocation:
	//!
	//! ```
	//! use kernel::{
	//! gpu::buddy::{
	//! GpuBuddy,
	//! GpuBuddyAllocFlags,
	//! GpuBuddyAllocMode,
	//! GpuBuddyParams, //
	//! },
	//! prelude::*,
	//! ptr::Alignment,
	//! sizes::*, //
	//! };
	//!
	//! // Create a 1GB buddy allocator with 4KB minimum chunk size.
	//! let buddy = GpuBuddy::new(GpuBuddyParams {
	//! base_offset: 0,
	//! size: SZ_1G as u64,
	//! chunk_size: Alignment::new::<SZ_4K>(),
	//! })?;
	//!
	//! assert_eq!(buddy.size(), SZ_1G as u64);
	//! assert_eq!(buddy.chunk_size(), Alignment::new::<SZ_4K>());
	//! let initial_free = buddy.avail();
	//!
	//! // Allocate 16MB. Block lands at the top of the address range.
	//! let allocated = KBox::pin_init(
	//! buddy.alloc_blocks(
	//! GpuBuddyAllocMode::Simple,
	//! SZ_16M as u64,
	//! Alignment::new::<SZ_16M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
	//!
	//! let block = allocated.iter().next().expect("expected one block");
	//! assert_eq!(block.offset(), (SZ_1G - SZ_16M) as u64);
	//! assert_eq!(block.order(), 12); // 2^12 pages = 16MB
	//! assert_eq!(block.size(), SZ_16M as u64);
	//! assert_eq!(allocated.iter().count(), 1);
	//!
	//! // Dropping the allocation returns the range to the buddy allocator.
	//! drop(allocated);
	//! assert_eq!(buddy.avail(), initial_free);
	//! # Ok::<(), Error>(())
	//! ```
	//!
	//! Top-down allocation allocates from the highest addresses:
	//!
	//! ```
	//! # use kernel::{
	//! # gpu::buddy::{GpuBuddy, GpuBuddyAllocMode, GpuBuddyAllocFlags, GpuBuddyParams},
	//! # prelude::*,
	//! # ptr::Alignment,
	//! # sizes::*, //
	//! # };
	//! # let buddy = GpuBuddy::new(GpuBuddyParams {
	//! # base_offset: 0,
	//! # size: SZ_1G as u64,
	//! # chunk_size: Alignment::new::<SZ_4K>(),
	//! # })?;
	//! # let initial_free = buddy.avail();
	//! let topdown = KBox::pin_init(
	//! buddy.alloc_blocks(
	//! GpuBuddyAllocMode::TopDown,
	//! SZ_16M as u64,
	//! Alignment::new::<SZ_16M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
	//!
	//! let block = topdown.iter().next().expect("expected one block");
	//! assert_eq!(block.offset(), (SZ_1G - SZ_16M) as u64);
	//! assert_eq!(block.order(), 12);
	//! assert_eq!(block.size(), SZ_16M as u64);
	//!
	//! // Dropping the allocation returns the range to the buddy allocator.
	//! drop(topdown);
	//! assert_eq!(buddy.avail(), initial_free);
	//! # Ok::<(), Error>(())
	//! ```
	//!
	//! Non-contiguous allocation can fill fragmented memory by returning multiple
	//! blocks:
	//!
	//! ```
	//! # use kernel::{
	//! # gpu::buddy::{
	//! # GpuBuddy, GpuBuddyAllocFlags, GpuBuddyAllocMode, GpuBuddyParams,
	//! # },
	//! # prelude::*,
	//! # ptr::Alignment,
	//! # sizes::*, //
	//! # };
	//! # let buddy = GpuBuddy::new(GpuBuddyParams {
	//! # base_offset: 0,
	//! # size: SZ_1G as u64,
	//! # chunk_size: Alignment::new::<SZ_4K>(),
	//! # })?;
	//! # let initial_free = buddy.avail();
	//! // Create fragmentation by allocating 4MB blocks at [0,4M) and [8M,12M).
	//! let frag1 = KBox::pin_init(
	//! buddy.alloc_blocks(
	//! GpuBuddyAllocMode::Range(0..SZ_4M as u64),
	//! SZ_4M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//! assert_eq!(buddy.avail(), initial_free - SZ_4M as u64);
	//!
	//! let frag2 = KBox::pin_init(
	//! buddy.alloc_blocks(
	//! GpuBuddyAllocMode::Range(SZ_8M as u64..(SZ_8M + SZ_4M) as u64),
	//! SZ_4M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//! assert_eq!(buddy.avail(), initial_free - SZ_8M as u64);
	//!
	//! // Allocate 8MB, this returns 2 blocks from the holes.
	//! let fragmented = KBox::pin_init(
	//! buddy.alloc_blocks(
	//! GpuBuddyAllocMode::Range(0..SZ_16M as u64),
	//! SZ_8M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//! assert_eq!(buddy.avail(), initial_free - SZ_16M as u64);
	//!
	//! let (mut count, mut total) = (0u32, 0u64);
	//! for block in fragmented.iter() {
	//! assert_eq!(block.size(), SZ_4M as u64);
	//! total += block.size();
	//! count += 1;
	//! }
	//! assert_eq!(total, SZ_8M as u64);
	//! assert_eq!(count, 2);
	//! # Ok::<(), Error>(())
	//! ```
	//!
	//! Contiguous allocation fails when only fragmented space is available:
	//!
	//! ```
	//! # use kernel::{
	//! # gpu::buddy::{
	//! # GpuBuddy, GpuBuddyAllocFlag, GpuBuddyAllocFlags, GpuBuddyAllocMode, GpuBuddyParams,
	//! # },
	//! # prelude::*,
	//! # ptr::Alignment,
	//! # sizes::*, //
	//! # };
	//! // Create a small 16MB buddy allocator with fragmented memory.
	//! let small = GpuBuddy::new(GpuBuddyParams {
	//! base_offset: 0,
	//! size: SZ_16M as u64,
	//! chunk_size: Alignment::new::<SZ_4K>(),
	//! })?;
	//!
	//! let _hole1 = KBox::pin_init(
	//! small.alloc_blocks(
	//! GpuBuddyAllocMode::Range(0..SZ_4M as u64),
	//! SZ_4M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//!
	//! let _hole2 = KBox::pin_init(
	//! small.alloc_blocks(
	//! GpuBuddyAllocMode::Range(SZ_8M as u64..(SZ_8M + SZ_4M) as u64),
	//! SZ_4M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlags::default(),
	//! ),
	//! GFP_KERNEL,
	//! )?;
	//!
	//! // 8MB contiguous should fail, only two non-contiguous 4MB holes exist.
	//! let result = KBox::pin_init(
	//! small.alloc_blocks(
	//! GpuBuddyAllocMode::Simple,
	//! SZ_8M as u64,
	//! Alignment::new::<SZ_4M>(),
	//! GpuBuddyAllocFlag::Contiguous,
	//! ),
	//! GFP_KERNEL,
	//! );
	//! assert!(result.is_err());
	//! # Ok::<(), Error>(())
	//! ```

	use core::ops::Range;

	use crate::{
	bindings,
	clist_create,
	error::to_result,
	interop::list::CListHead,
	new_mutex,
	prelude::*,
	ptr::Alignment,
	sync::{
	lock::mutex::MutexGuard,
	Arc,
	Mutex, //
	},
	types::Opaque, //
	};

	/// Allocation mode for the GPU buddy allocator.
	///
	/// The mode determines the primary allocation strategy. Modes are mutually
	/// exclusive: an allocation is either simple, range-constrained, or top-down.
	///
	/// Orthogonal modifier flags (e.g., contiguous, clear) are specified separately
	/// via [`GpuBuddyAllocFlags`].
	#[derive(Clone, Debug, PartialEq, Eq)]
	pub enum GpuBuddyAllocMode {
	/// Simple allocation without constraints.
	Simple,
	/// Range-based allocation within the given address range.
	Range(Range<u64>),
	/// Allocate from top of address space downward.
	TopDown,
	}

	impl GpuBuddyAllocMode {
	/// Returns the C flags corresponding to the allocation mode.
	fn as_flags(&self) -> usize {
	match self {
	Self::Simple => 0,
	Self::Range(_) => bindings::GPU_BUDDY_RANGE_ALLOCATION,
	Self::TopDown => bindings::GPU_BUDDY_TOPDOWN_ALLOCATION,
	}
	}

	/// Extracts the range start/end, defaulting to `(0, 0)` for non-range modes.
	fn range(&self) -> (u64, u64) {
	match self {
	Self::Range(range) => (range.start, range.end),
	_ => (0, 0),
	}
	}
	}

	crate::impl_flags!(
	/// Modifier flags for GPU buddy allocation.
	///
	/// These flags can be combined with any [`GpuBuddyAllocMode`] to control
	/// additional allocation behavior.
	#[derive(Clone, Copy, Default, PartialEq, Eq)]
	pub struct GpuBuddyAllocFlags(usize);

	/// Individual modifier flag for GPU buddy allocation.
	#[derive(Clone, Copy, PartialEq, Eq)]
	pub enum GpuBuddyAllocFlag {
	/// Allocate physically contiguous blocks.
	Contiguous = bindings::GPU_BUDDY_CONTIGUOUS_ALLOCATION,

	/// Request allocation from cleared (zeroed) memory.
	Clear = bindings::GPU_BUDDY_CLEAR_ALLOCATION,

	/// Disable trimming of partially used blocks.
	TrimDisable = bindings::GPU_BUDDY_TRIM_DISABLE,
	}
	);

	/// Parameters for creating a GPU buddy allocator.
	pub struct GpuBuddyParams {
	/// Base offset (in bytes) where the managed memory region starts.
	/// Allocations will be offset by this value.
	pub base_offset: u64,
	/// Total size (in bytes) of the address space managed by the allocator.
	pub size: u64,
	/// Minimum allocation unit / chunk size; must be >= 4KB.
	pub chunk_size: Alignment,
	}

	/// Inner structure holding the actual buddy allocator.
	///
	/// # Synchronization
	///
	/// The C `gpu_buddy` API requires synchronization (see `include/linux/gpu_buddy.h`).
	/// Internal locking ensures all allocator and free operations are properly
	/// synchronized, preventing races between concurrent allocations and the
	/// freeing that occurs when [`AllocatedBlocks`] is dropped.
	///
	/// # Invariants
	///
	/// The inner [`Opaque`] contains an initialized buddy allocator.
	#[pin_data(PinnedDrop)]
	struct GpuBuddyInner {
	#[pin]
	inner: Opaque<bindings::gpu_buddy>,

	// TODO: Replace `Mutex<()>` with `Mutex<Opaque<..>>` once `Mutex::new()`
	// accepts `impl PinInit<T>`.
	#[pin]
	lock: Mutex<()>,
	/// Cached creation parameters (do not change after init).
	params: GpuBuddyParams,
	}

	impl GpuBuddyInner {
	/// Create a pin-initializer for the buddy allocator.
	fn new(params: GpuBuddyParams) -> impl PinInit<Self, Error> {
	let size = params.size;
	let chunk_size = params.chunk_size;

	// INVARIANT: `gpu_buddy_init` returns 0 on success, at which point the
	// `gpu_buddy` structure is initialized and ready for use with all
	// `gpu_buddy_*` APIs. `try_pin_init!` only completes if all fields succeed,
	// so the invariant holds when construction finishes.
	try_pin_init!(Self {
	inner <- Opaque::try_ffi_init(\|ptr\| {
	// SAFETY: `ptr` points to valid uninitialized memory from the pin-init
	// infrastructure. `gpu_buddy_init` will initialize the structure.
	to_result(unsafe {
	bindings::gpu_buddy_init(ptr, size, chunk_size.as_usize() as u64)
	})
	}),
	lock <- new_mutex!(()),
	params,
	})
	}

	/// Lock the mutex and return a guard for accessing the allocator.
	fn lock(&self) -> GpuBuddyGuard<'_> {
	GpuBuddyGuard {
	inner: self,
	_guard: self.lock.lock(),
	}
	}
	}

	#[pinned_drop]
	impl PinnedDrop for GpuBuddyInner {
	fn drop(self: Pin<&mut Self>) {
	let guard = self.lock();

	// SAFETY: Per the type invariant, `inner` contains an initialized
	// allocator. `guard` provides exclusive access.
	unsafe { bindings::gpu_buddy_fini(guard.as_raw()) };
	}
	}

	// SAFETY: `GpuBuddyInner` can be sent between threads.
	unsafe impl Send for GpuBuddyInner {}

	// SAFETY: `GpuBuddyInner` is `Sync` because `GpuBuddyInner::lock`
	// serializes all access to the C allocator, preventing data races.
	unsafe impl Sync for GpuBuddyInner {}

	/// Guard that proves the lock is held, enabling access to the allocator.
	///
	/// The `_guard` holds the lock for the duration of this guard's lifetime.
	struct GpuBuddyGuard<'a> {
	inner: &'a GpuBuddyInner,
	_guard: MutexGuard<'a, ()>,
	}

	impl GpuBuddyGuard<'_> {
	/// Get a raw pointer to the underlying C `gpu_buddy` structure.
	fn as_raw(&self) -> *mut bindings::gpu_buddy {
	self.inner.inner.get()
	}
	}

	/// GPU buddy allocator instance.
	///
	/// This structure wraps the C `gpu_buddy` allocator using reference counting.
	/// The allocator is automatically cleaned up when all references are dropped.
	///
	/// Refer to the module-level documentation for usage examples.
	pub struct GpuBuddy(Arc<GpuBuddyInner>);

	impl GpuBuddy {
	/// Create a new buddy allocator.
	///
	/// The allocator manages a contiguous address space of the given size, with the
	/// specified minimum allocation unit (chunk_size must be at least 4KB).
	pub fn new(params: GpuBuddyParams) -> Result<Self> {
	Arc::pin_init(GpuBuddyInner::new(params), GFP_KERNEL).map(Self)
	}

	/// Get the base offset for allocations.
	pub fn base_offset(&self) -> u64 {
	self.0.params.base_offset
	}

	/// Get the chunk size (minimum allocation unit).
	pub fn chunk_size(&self) -> Alignment {
	self.0.params.chunk_size
	}

	/// Get the total managed size.
	pub fn size(&self) -> u64 {
	self.0.params.size
	}

	/// Get the available (free) memory in bytes.
	pub fn avail(&self) -> u64 {
	let guard = self.0.lock();

	// SAFETY: Per the type invariant, `inner` contains an initialized allocator.
	// `guard` provides exclusive access.
	unsafe { (*guard.as_raw()).avail }
	}

	/// Allocate blocks from the buddy allocator.
	///
	/// Returns a pin-initializer for [`AllocatedBlocks`].
	pub fn alloc_blocks(
	&self,
	mode: GpuBuddyAllocMode,
	size: u64,
	min_block_size: Alignment,
	flags: impl Into<GpuBuddyAllocFlags>,
	) -> impl PinInit<AllocatedBlocks, Error> {
	let buddy_arc = Arc::clone(&self.0);
	let (start, end) = mode.range();
	let mode_flags = mode.as_flags();
	let modifier_flags = flags.into();

	// Create pin-initializer that initializes list and allocates blocks.
	try_pin_init!(AllocatedBlocks {
	buddy: buddy_arc,
	list <- CListHead::new(),
	_: {
	// Reject zero-sized or inverted ranges.
	if let GpuBuddyAllocMode::Range(range) = &mode {
	if range.is_empty() {
	Err::<(), Error>(EINVAL)?;
	}
	}

	// Lock while allocating to serialize with concurrent frees.
	let guard = buddy.lock();

	// SAFETY: Per the type invariant, `inner` contains an initialized
	// allocator. `guard` provides exclusive access.
	to_result(unsafe {
	bindings::gpu_buddy_alloc_blocks(
	guard.as_raw(),
	start,
	end,
	size,
	min_block_size.as_usize() as u64,
	list.as_raw(),
	mode_flags \| usize::from(modifier_flags),
	)
	})?
	}
	})
	}
	}

	/// Allocated blocks from the buddy allocator with automatic cleanup.
	///
	/// This structure owns a list of allocated blocks and ensures they are
	/// automatically freed when dropped. Use `iter()` to iterate over all
	/// allocated blocks.
	///
	/// # Invariants
	///
	/// - `list` is an initialized, valid list head containing allocated blocks.
	#[pin_data(PinnedDrop)]
	pub struct AllocatedBlocks {
	#[pin]
	list: CListHead,
	buddy: Arc<GpuBuddyInner>,
	}

	impl AllocatedBlocks {
	/// Check if the block list is empty.
	pub fn is_empty(&self) -> bool {
	// An empty list head points to itself.
	!self.list.is_linked()
	}

	/// Iterate over allocated blocks.
	///
	/// Returns an iterator yielding [`AllocatedBlock`] values. Each [`AllocatedBlock`]
	/// borrows `self` and is only valid for the duration of that borrow.
	pub fn iter(&self) -> impl Iterator<Item = AllocatedBlock<'_>> + '_ {
	let head = self.list.as_raw();
	// SAFETY: Per the type invariant, `list` is an initialized sentinel `list_head`
	// and is not concurrently modified (we hold a `&self` borrow). The list contains
	// `gpu_buddy_block` items linked via `__bindgen_anon_1.link`. `Block` is
	// `#[repr(transparent)]` over `gpu_buddy_block`.
	let clist = unsafe {
	clist_create!(
	head,
	Block,
	bindings::gpu_buddy_block,
	__bindgen_anon_1.link
	)
	};

	clist
	.iter()
	.map(\|this\| AllocatedBlock { this, blocks: self })
	}
	}

	#[pinned_drop]
	impl PinnedDrop for AllocatedBlocks {
	fn drop(self: Pin<&mut Self>) {
	let guard = self.buddy.lock();

	// SAFETY:
	// - list is valid per the type's invariants.
	// - guard provides exclusive access to the allocator.
	unsafe {
	bindings::gpu_buddy_free_list(guard.as_raw(), self.list.as_raw(), 0);
	}
	}
	}

	/// A GPU buddy block.
	///
	/// Transparent wrapper over C `gpu_buddy_block` structure. This type is returned
	/// as references during iteration over [`AllocatedBlocks`].
	///
	/// # Invariants
	///
	/// The inner [`Opaque`] contains a valid, allocated `gpu_buddy_block`.
	#[repr(transparent)]
	struct Block(Opaque<bindings::gpu_buddy_block>);

	impl Block {
	/// Get a raw pointer to the underlying C block.
	fn as_raw(&self) -> *mut bindings::gpu_buddy_block {
	self.0.get()
	}

	/// Get the block's raw offset in the buddy address space (without base offset).
	fn offset(&self) -> u64 {
	// SAFETY: `self.as_raw()` is valid per the type's invariants.
	unsafe { bindings::gpu_buddy_block_offset(self.as_raw()) }
	}

	/// Get the block order.
	fn order(&self) -> u32 {
	// SAFETY: `self.as_raw()` is valid per the type's invariants.
	unsafe { bindings::gpu_buddy_block_order(self.as_raw()) }
	}
	}

	// SAFETY: `Block` is a wrapper around `gpu_buddy_block` which can be
	// sent across threads safely.
	unsafe impl Send for Block {}

	// SAFETY: `Block` is only accessed through shared references after
	// allocation, and thus safe to access concurrently across threads.
	unsafe impl Sync for Block {}

	/// A buddy block paired with its owning [`AllocatedBlocks`] context.
	///
	/// Unlike a raw block, which only knows its offset within the buddy address
	/// space, an [`AllocatedBlock`] also has access to the allocator's `base_offset`
	/// and `chunk_size`, enabling it to compute absolute offsets and byte sizes.
	///
	/// Returned by [`AllocatedBlocks::iter()`].
	pub struct AllocatedBlock<'a> {
	this: &'a Block,
	blocks: &'a AllocatedBlocks,
	}

	impl AllocatedBlock<'_> {
	/// Get the block's offset in the address space.
	///
	/// Returns the absolute offset including the allocator's base offset.
	/// This is the actual address to use for accessing the allocated memory.
	pub fn offset(&self) -> u64 {
	self.blocks.buddy.params.base_offset + self.this.offset()
	}

	/// Get the block order (size = chunk_size << order).
	pub fn order(&self) -> u32 {
	self.this.order()
	}

	/// Get the block's size in bytes.
	pub fn size(&self) -> u64 {
	(self.blocks.buddy.params.chunk_size.as_usize() as u64) << self.this.order()
	}
	}