OSDev.org

I was thinking that when using memory blocks intended to change size, it could probably be good to use:

- A variable to define memory chunk sizes, as in sectors or pages.

- A small region, maybe 512 bytes in size, to hold a set of chunk pointers. The first pointer element would point to the previous list of pointers. The last pointer element would point to the next list of pointers. The pointers would be word-sized depending on the CPU mode (16, 20, 32 or 64-bit).

- Then we would allocate memory using the system facilities. For each actual data chunk that we reserved, we would records its pointer in the current pointer list element that is free.


This is intended to be sequential. It's intended to emulate a non-fragmented address space by using associated functions that can read and join through chunk boundaries, as in a sector or cluster on disk. It's not intended to delete or insert associated pointer elements in the middle of the associated pointer lists.

I remember that static things like GIF data are defined in chunks where the first byte tells us how many more bytes follow the current chunk. Then there is compressed data bytes. So similarly we could keep a list of pointers for data chunks of a known size. Just like a compressed or non-compressed image, memory is sequential and non-fragmented at its hardware level, so this is the first thing to ensure to preserve before trying to use any other algorithm.

If we are to deal with non-dynamic data, it would probably be acceptable to just allocate a data buffer with enough size to hold that data at once. It could be made non-fragmented with the virtualization of paging. But seeing how it would preserve more memory and would guard in the future against any fragmentation at the application level, it would probably be best to always allocate by fragments like this or a similar primitive way. In many cases it could probably be better to have the pointers to actual data point to offsets on disk, not in memory.

Whenever possible, it seems to be better to access data, read or write, from disk, small chunks at a time, instead of expecting big data sets to be swapped back to disk. It seems that the vast majority of cases can be managed from disk without ever having to load that much data into RAM. which would make for much more economic programs.


If we wanted more advanced dynamic data-keeping algorithms we would need to embed several things:

1. Paging, or full address space for the currently executing code.

2. This algorithm to add lists of pointers for sequential data representation in fragmented memory chunks.

3. The more advanced, more dynamic memory algorithms and structures would need to be embedded in the previous 2 levels. After overcoming physical fragmentation with paging and virtual fragmentation with associated lists of pointers, we are free to implement any other more advanced data structure using the foundation of the previous 2 lower-level memory sanitizing layers.

__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
As for paging we could probably:

- Format the memory, reserving a contiguous space for CPU paging structures whose size would depend on installed RAM, reserved at system start up time. Just like in a disk, we would format the memory using whatever format paging expects; would then keep a record of the number of clusters and memory size. Then we could keep track of how much memory is free at all times whenever we allocate or free system-wide pages.

- As part of the kernel-level paging formatting of RAM, it would probably be necessary to create an area that is intended to hold associated pointers to pages, defining at least enough pointer space for dynamically allocating more later by the kernel memory management.

______________________
For being able to freely read chunks of memory that are fragmented at our normal level of access we would probably need a sort of functions, similar to HTML5 Data Views, but with the capability to interpret and manipulate the data as if it was really contiguous.

Then we could use that data-viewing set of functions to implement any other structure like linked lists, binary trees, and other things where we could arbitrarily add at the start, the end, insert, or delete in the middle...

I think that the goal is being able to make a data set, variable, buffer, etc., see the address space as if it was the only thing present, as if the address space was unlimited, unfragmented, unfragmentable and flexible to add or delete data of arbitrary sizes at any point without ever finding anything else on the way.

Nowadays, the FPU could probably be used to keep track and actually access big address spaces like 48-bit LBA, 64-bit file sizes, and the like.

After analyzing how it would actually go when implemented, I think that we could initially do the following:

- Once the kernel is booted, we could create a contiguous bit map where each bit would correspond to a physical 4KB page. A 0 would mean a free page, an 1 an used page. The size of this bit map would depend on the detected RAM size.

- There would be a function that would only initialize and return a pointer to a 512-byte pointer array, maybe called CreateChunkedBuffer.

- Then we would have a function that would allow us to specify the number of 4096 pages in the fragmented buffer, called SetChunkedBufferSize, with which we could resize the buffer, shrinking or enlarging it as a sequential buffer, as when adding or truncating to a file found in a physical starting sector.

- We could then have primitive functions to read, write, compare, search, etc., the contents in this buffer.

- With this we could implement more complex dynamic data types.

- To deallocate, we could have a function called FreeChunkedBuffer, and what it would do would be to traverse all chained 512-byte lists of buffer fragments, end to start, and for each fragment address it would set the bit in the system, or maybe local, page bit map to 0 to free that page. In the end, the system page containing any pointer arrays to buffer fragments would also be set to 0 to free them down to the initial pointer array 512-byte area.


It could probably be first attempted when loading a program, marking the bits for the pages where it is with 1, and the same for kernel areas and special memory ranges, like the first Megabyte. Then the program could make use of the aforementioned functions to perform some task with dynamically-sized data, like displaying a graphic or reading a text file or directory.

So the memory would normally be accessed indirectly through this layer of functions to ensure that no fragmentation affects each of the buffers we need to create. It would be protecting it against fragmentation at the physical and the virtual level, so that category of functions should be implemented or be accessible at those two levels.

The whole memory should be formatted with something like this by the kernel when nothing else but itself has been loaded, and then each additional virtual address space should also be formatted in this way for being able to implement protection against fragmentation and the capability to resize the allocated memory dynamically per each allocated buffer at run time. The programs and the kernel would each probably need to have a static data area for being able to expand dynamically from there.