Allocating for sizes way beyond the heap size seems buggy

[andre-richter]

So I am using this crate now in https://github.com/rust-embedded/rust-raspberrypi-OS-tutorials/tree/master/19_kernel_heap (thanks for the crate!!).

The heap size provided in the tutorial is 16 MiB. I realized that when I try to allocate for something ridiculously large, e.g. 12 GiB, I don't get an allocation error, but a data abort exactly here: https://github.com/phil-opp/linked-list-allocator/blob/master/src/hole.rs#L271. Maybe some math going wrong?

Can be reproduced by adding an allocation for something this large at the end of main.rs and then run make qemu (needs docker). I am currently a bit short on time, so sorry for not investigating myself.

[jamesmunns]

Thanks for the repro instructions @andre-richter! I think I fixed this indirectly due to some work in the internal logic.

With this patch:

diff --git a/19_kernel_heap/Makefile b/19_kernel_heap/Makefile
index c9a7d59..0881eff 100644
--- a/19_kernel_heap/Makefile
+++ b/19_kernel_heap/Makefile
@@ -205,8 +205,7 @@ $(KERNEL_ELF_TTABLES): $(KERNEL_ELF_TTABLES_DEPS)
 ##------------------------------------------------------------------------------
 $(KERNEL_ELF_TTABLES_SYMS): $(KERNEL_ELF_TTABLES_SYMS_DEPS)
 	$(call color_header, "Generating kernel symbols and patching kernel ELF")
-	@time -f "in %es" \
-                $(MAKE) --no-print-directory -f kernel_symbols.mk
+	$(MAKE) --no-print-directory -f kernel_symbols.mk
 
 ##------------------------------------------------------------------------------
 ## Generate the stripped kernel binary
diff --git a/19_kernel_heap/kernel/Cargo.toml b/19_kernel_heap/kernel/Cargo.toml
index 2f5d059..6725251 100644
--- a/19_kernel_heap/kernel/Cargo.toml
+++ b/19_kernel_heap/kernel/Cargo.toml
@@ -18,7 +18,7 @@ test_build = ["qemu-exit"]
 [dependencies]
 test-types = { path = "../libraries/test-types" }
 debug-symbol-types = { path = "../libraries/debug-symbol-types" }
-linked_list_allocator = { version = "0.9.x", default-features = false, features = ["const_mut_refs"] }
+# linked_list_allocator = { version = "0.9.x", default-features = false, features = ["const_mut_refs"] }
 
 # Optional dependencies
 tock-registers = { version = "0.7.x", default-features = false, features = ["register_types"], optional = true }
@@ -28,6 +28,13 @@ qemu-exit = { version = "3.x.x", optional = true }
 [target.'cfg(target_arch = "aarch64")'.dependencies]
 cortex-a = { version = "7.x.x" }
 
+[dependencies.linked_list_allocator]
+# version = "0.9.x"
+git = "https://github.com/jamesmunns/linked-list-allocator"
+rev = "085c26426f06909560a7069f72253192440bdef4"
+default-features = false
+features = ["const_mut_refs"]
+
 ##--------------------------------------------------------------------------------------------------
 ## Testing
 ##--------------------------------------------------------------------------------------------------
diff --git a/19_kernel_heap/kernel/src/main.rs b/19_kernel_heap/kernel/src/main.rs
index d2044c2..070d7eb 100644
--- a/19_kernel_heap/kernel/src/main.rs
+++ b/19_kernel_heap/kernel/src/main.rs
@@ -15,6 +15,8 @@
 
 extern crate alloc;
 
+use core::alloc::{GlobalAlloc, Layout};
+
 use libkernel::{bsp, cpu, driver, exception, info, memory, state, time, warn};
 
 /// Early init code.
@@ -97,6 +99,18 @@ fn kernel_main() -> ! {
     info!("Kernel heap:");
     memory::heap_alloc::kernel_heap_allocator().print_usage();
 
+    let ptr = unsafe {
+        let layout = Layout::from_size_align(usize::MAX / 4, 4).unwrap();
+        memory::heap_alloc::kernel_heap_allocator().alloc(layout)
+    };
+
+    if ptr == core::ptr::null_mut() {
+        info!("big alloc is a null");
+    } else {
+        info!("unpossible!");
+    }
+
+
     info!("Echoing input now");
     cpu::wait_forever();
 }
diff --git a/19_kernel_heap/kernel/src/memory/heap_alloc.rs b/19_kernel_heap/kernel/src/memory/heap_alloc.rs
index 81a5009..c658fdc 100644
--- a/19_kernel_heap/kernel/src/memory/heap_alloc.rs
+++ b/19_kernel_heap/kernel/src/memory/heap_alloc.rs
@@ -133,5 +133,5 @@ pub fn kernel_init_heap_allocator() {
 
     KERNEL_HEAP_ALLOCATOR
         .inner
-        .lock(|inner| unsafe { inner.init(region.start_addr().as_usize(), region.size()) });
+        .lock(|inner| unsafe { inner.init(region.start_addr().as_usize() as *mut u8, region.size()) });
 }

I now get the correct output:

[    0.022491] Drivers loaded:
[    0.022731]       1. BCM PL011 UART
[    0.022975]       2. BCM GPIO
[    0.023126]       3. BCM Interrupt Controller
[    0.023373] Registered IRQ handlers:
[    0.023742]       Peripheral handler:
[    0.024048]              57. BCM PL011 UART
[    0.024384] Kernel heap:
[    0.024701]       Used: 2512 Byte (3 KiB)
[    0.025090]       Free: 16774704 Byte (16 MiB)
[    0.025571] big alloc is a null
[    0.025778] Echoing input now
qemu-system-aarch64: terminating on signal 2

[andre-richter]

Thanks, @jamesmunns, awesome work!

Can confirm that with your changes, it triggers the allocation error handler properly now:

diff --git a/19_kernel_heap/kernel/src/main.rs b/19_kernel_heap/kernel/src/main.rs
index d2044c2..8772582 100644
--- a/19_kernel_heap/kernel/src/main.rs
+++ b/19_kernel_heap/kernel/src/main.rs
@@ -97,6 +97,9 @@ fn kernel_main() -> ! {
     info!("Kernel heap:");
     memory::heap_alloc::kernel_heap_allocator().print_usage();
 
+    let x = alloc::boxed::Box::new([1u8; 12 * 1024 * 1024 * 1024]);
+    info!("{}", x[0]);
+
     info!("Echoing input now");
     cpu::wait_forever();
 }

[    0.110631] Kernel heap:
[    0.110858]       Used: 2512 Byte (3 KiB)
[    0.111277]       Free: 16774704 Byte (16 MiB)
[    0.111795] Kernel panic!

Panic location:
      File 'kernel/src/memory/heap_alloc.rs', line 65, column 5

Allocation error: Layout { size_: 12884901888, align_: 1 (1 << 0) }

Backtrace:
      ----------------------------------------------------------------------------------------------
          Address            Function containing address
      ----------------------------------------------------------------------------------------------
       1. ffffffffc000cd18 | <libkernel::bsp::device_driver::bcm::bcm2xxx_pl011_uart::PL011Uart as libkernel::console::interface::Write>::write_fmt
       2. ffffffffc000d218 | libkernel::print::_print                          
       3. ffffffffc000d1b0 | rust_begin_unwind                                 
       4. ffffffffc0004ca0 | core::panicking::panic_fmt                        
       5. ffffffffc000b4a8 | rust_oom                                          
       6. ffffffffc0002f78 | __rg_oom                                          
       7. ffffffffc000e420 | __rust_alloc_error_handler                        
       8. ffffffffc0002f68 | core::ops::function::FnOnce::call_once            
       9. ffffffffc0002f58 | core::intrinsics::const_eval_select               
      10. ffffffffc0002f38 | alloc::alloc::handle_alloc_error                  
      11. ffffffffc0002ee8 | kernel::kernel_main                               
      12. ffffffffc0001724 | kernel_init                                       
      ----------------------------------------------------------------------------------------------

qemu-system-aarch64: terminating on signal 2

[phil-opp]

Thanks for the update @andre-richter (and of course thanks for the fix @jamesmunns)!

On an unrelated note, I just moved the project to the rust-osdev organization to make shared maintenance easier. So if one of you is interested in maintaining this crate and/or developing it further, just let me know!