ChatGPT is legitimately, jaw droppingly, not even funny anymore mind blowing
I was trying to see if I could get ChatGPT to write a simple extent traversal algorithm for writing data to disk in an OS project. TL;DR, that failed. It doesn't seem to understand higher level concepts (extents specifically). But! The project also needs a bitmap allocator to track used data blocks and inodes, so I gave that a go and the results blew my mind.
For context, the project is written in C and already has a bitmap allocator, but still, if you haven't tried ChatGPT then nothing I say in words can express the feeling you'll get when it spits code that would have taken an hour or two to write in ~1 min. Now that the rush is over, I'm seeing a lot of flaws that would need to be cleaned up, but for prototyping this is incredible.
Final code in the playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f935cf99337c5c401ba0eb2122607a1
Without further ado, the transcript.
Write balloc and bfree functions that perform bitmap allocation and deallocation
To implement bitmap allocation and deallocation, we can use two simple functions: balloc() and bfree().
Here is an example of how these functions might be implemented:
// Function to allocate a bit in a bitmap
int balloc(int *bitmap, int size)
{
// Iterate over the bitmap
for (int i = 0; i < size; i++)
{
// If the current bit is 0 (unallocated)
if (bitmap[i] == 0)
{
// Set the bit to 1 (allocated) and return the index
bitmap[i] = 1;
return i;
}
}
// If no bits are available, return -1
return -1;
}
// Function to free a bit in a bitmap
void bfree(int *bitmap, int index)
{
// Set the bit at the specified index to 0 (unallocated)
bitmap[index] = 0;
}
These functions use a simple linear search to find the first unallocated bit in the bitmap, and set it to 1 to indicate that it has been allocated. The bfree() function simply sets the bit at the specified index back to 0 to indicate that it is now unallocated.
In this example, the bitmap parameter is a pointer to an array of integers that represent the bits in the bitmap, and size is the number of bits in the bitmap. The index parameter in the bfree() function is the index of the bit that should be freed.
Use each bit in the int to minimize wasted space
To minimize wasted space when using a bitmap, we can use each bit in an integer to represent a bit in the bitmap. For example, if we have a bitmap with 8 bits, we can use a single integer to store those bits.
Here is an example of how we might implement this using the balloc() and bfree() functions from the previous answer:
#define BITS_PER_INT (sizeof(int) * 8)
// Function to allocate a bit in a bitmap
int balloc(int *bitmap, int size)
{
// Iterate over the bitmap
for (int i = 0; i < size; i++)
{
// Calculate the index of the integer and the bit within the integer
int int_index = i / BITS_PER_INT;
int bit_index = i % BITS_PER_INT;
// If the current bit is 0 (unallocated)
if ((bitmap[int_index] & (1 << bit_index)) == 0)
{
// Set the bit to 1 (allocated) and return the index
bitmap[int_index] |= (1 << bit_index);
return i;
}
}
// If no bits are available, return -1
return -1;
}
// Function to free a bit in a bitmap
void bfree(int *bitmap, int index)
{
// Calculate the index of the integer and the bit within the integer
int int_index = index / BITS_PER_INT;
int bit_index = index % BITS_PER_INT;
// Set the bit at the specified index to 0 (unallocated)
bitmap[int_index] &= ~(1 << bit_index);
}
In this example, we use a constant called BITS_PER_INT to determine how many bits can be stored in a single integer. We then use integer division and modulo operations to calculate the index of the integer in the bitmap array that contains the bit we want to allocate or free, as well as the index of the bit within that integer.
Once we have these indices, we use bitwise operations to set or clear the appropriate bit in the integer. This allows us to use each bit in an integer to represent a bit in the bitmap, which minimizes wasted space.
Now support allocating and deallocating multiple bits at a time with a parameter called count that specifies the number of bits to alloc/dealloc
To support allocating and deallocating multiple bits at a time, we can modify the balloc() and bfree() functions to take an additional count parameter that specifies the number of bits to allocate or free.
Here is an example of how these functions might be implemented with this added support:
#define BITS_PER_INT (sizeof(int) * 8)
// Function to allocate a bit in a bitmap
int balloc(int *bitmap, int size, int count)
{
// Iterate over the bitmap
for (int i = 0; i < size; i++)
{
// Calculate the index of the integer and the bit within the integer
int int_index = i / BITS_PER_INT;
int bit_index = i % BITS_PER_INT;
// If the current bit is 0 (unallocated)
if ((bitmap[int_index] & (1 << bit_index)) == 0)
{
// Check if the next `count` bits are also unallocated
int j;
for (j = 1; j < count; j++)
{
int next_int_index = (i + j) / BITS_PER_INT;
int next_bit_index = (i + j) % BITS_PER_INT;
if ((bitmap[next_int_index] & (1 << next_bit_index)) != 0)
{
// If any of the next bits are allocated, stop checking
break;
}
}
// If all of the next bits are unallocated, allocate them and return the index
if (j == count)
{
for (j = 0; j < count; j++)
{
int next_int_index = (i + j) / BITS_PER_INT;
int next_bit_index = (i + j) % BITS_PER_INT;
bitmap[next_int_index] |= (1 << next_bit_index);
}
return i;
}
}
}
// If no bits are available, return -1
return -1;
}
// Function to free a bit in a bitmap
void bfree(int *bitmap, int index, int count)
{
// Iterate over the next `count` bits
for (int i = 0; i < count; i++)
{
// Calculate the index of the integer and the bit within the integer
int int_index = (index + i) / BITS_PER_INT;
int bit_index = (index + i) % BITS_PER_INT;
// Set the bit at the specified index to 0 (unallocated)
bitmap[int_index] &= ~(1 << bit_index);
}
}
In these updated functions, the count parameter specifies the number of bits to allocate or free. The balloc() function uses a nested loop to iterate over the next count bits in the bitmap, and checks if they are all unallocated. If they are, it sets them to 1 to indicate that they are now allocated. The bfree() function simply iterates over
Now write it in rust
To implement bitmap allocation and deallocation in Rust, we can use two simple functions: balloc() and bfree(). Here is an example of how these functions might be implemented:
const BITS_PER_INT: usize = 8 * std::mem::size_of::<i32>();
// Function to allocate a bit in a bitmap
fn balloc(bitmap: &mut [i32], size: usize, count: usize) -> Option<usize> {
// Iterate over the bitmap
for i in 0..size {
// Calculate the index of the integer and the bit within the integer
let int_index = i / BITS_PER_INT;
let bit_index = i % BITS_PER_INT;
// If the current bit is 0 (unallocated)
if (bitmap[int_index] & (1 << bit_index)) == 0 {
// Check if the next `count` bits are also unallocated
let mut j = 1;
while j < count {
let next_int_index = (i + j) / BITS_PER_INT;
let next_bit_index = (i + j) % BITS_PER_INT;
if (bitmap[next_int_index] & (1 << next_bit_index)) != 0 {
// If any of the next bits are allocated, stop checking
break;
}
j += 1;
}
// If all of the next bits are unallocated, allocate them and return the index
if j == count {
for j in 0..count {
let next_int_index = (i + j) / BITS_PER_INT;
let next_bit_index = (i + j) % BITS_PER_INT;
bitmap[next_int_index] |= (1 << next_bit_index);
}
return Some(i);
}
}
}
// If no bits are available, return None
None
}
// Function to free a bit in a bitmap
fn bfree(bitmap: &mut [i32], index: usize, count: usize) {
// Iterate over the next `count` bits
for i in 0..count {
// Calculate the index of the integer and the bit within the integer
let int_index = (index + i) / BITS_PER_INT;
let bit_index = (index + i) % BITS_PER_INT;
// Set the bit at the specified index to 0 (unallocated)
bitmap[int_index] &= !(1 << bit_index);
}
}
In this example, the bitmap parameter is a mutable slice of i32 values that represent the bits in the bitmap, and size is the number of bits in the bitmap. The count parameter specifies the number of bits to allocate or free. The index parameter in the bfree() function is the index of the first bit to free.
These functions use a simple linear search to find the first unallocated bit in the bitmap, and set it to 1 to indicate that it has been allocated. The `
Write a demo main fn that uses the allocator
Here is an example of a main() function that uses the balloc() and bfree() functions from the previous answer to allocate and deallocate bits in a bitmap:
fn main() {
let mut bitmap = [0, 0, 0];
let size = 3 * BITS_PER_INT;
// Allocate 3 bits
let index = balloc(&mut bitmap, size, 3).expect("no bits available");
println!("Allocated bits at index {}", index);
// Free the allocated bits
bfree(&mut bitmap, index, 3);
println!("Freed bits at index {}", index);
}
In this example, we create a bitmap with 3 integers (for a total of 3 * BITS_PER_INT bits). We then use the balloc() function to allocate 3 bits in the bitmap, and print the index of the first allocated bit. Finally, we use the bfree() function to free the allocated bits, and print the index of the first freed bit.
This main() function demonstrates how to use the balloc() and bfree() functions to allocate and deallocate bits in a bitmap.
Print the bits in the bitmap after every API call
To print the bits in the bitmap after every call to the balloc() and bfree() functions, we can modify the main() function to include a helper function that prints the bitmap. Here is an example of how this might be implemented:
fn main() {
let mut bitmap = [0, 0, 0];
let size = 3 * BITS_PER_INT;
// Allocate 3 bits
let index = balloc(&mut bitmap, size, 3).expect("no bits available");
println!("Allocated bits at index {}", index);
print_bitmap(&bitmap);
// Free the allocated bits
bfree(&mut bitmap, index, 3);
println!("Freed bits at index {}", index);
print_bitmap(&bitmap);
}
fn print_bitmap(bitmap: &[i32]) {
for i in bitmap {
for j in 0..BITS_PER_INT {
print!("{}", (i >> j) & 1);
}
println!();
}
}
In this example, we added a print_bitmap() function that iterates over the bitmap slice and prints each bit in the bitmap using a bitwise shift and mask operation.
In the main() function, we call this print_bitmap() function after each call to balloc() and bfree() to print the current state of the bitmap. This allows us to see how the allocation and deallocation operations affect the bits in the bitmap.