flat assembler
Message board for the users of flat assembler.

Index > OS Construction > Building a memory bitmap for 64bit

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
calpol2004



Joined: 16 Dec 2004
Posts: 110
calpol2004
EDIT: It just hit me...if i take the highest region of of memory from bios interrupt 0x15, the highest base region+size with its type set to available can tell me exactly how big my memory bitmap needs to be. Any other ideas?

Under 32bit mode its quite common to manage your physical memory into 4k blocks and have a bit in a bitmap specifying if its allocated or not. a bitmap for all pages that make up the 4GB address space only takes a mere 130kb of memory or so. you can then map your virtual memory space to these blocks by searching the bitmap for the first 0 and setting it to one and setting the virtual page to the physical page.

Of course with 64bit mode the story changes. its would be 130k multiplied by 2, 32 times. which is a large amount of memory Shocked.

The only reason that you have to map the whole 4GB address space in 32bit mode is because of holes. If you only map as much address space as the system has in memory then i wouldnt have to worry about it. But things like having a gap inbetween ram chips could screw this up.

Should i assume that there are no holes in memory, is this just a legacy thing with old memory controllers?

I'd also heard that 64bit systems cannnot actually truly access 2^64 bytes of their address space but only some of it (at the moment anyway). how wide is the address bus at the moment for 64bit systems? will it just ignore the upper bits?

How should i go about this?
Post 09 Dec 2008, 16:36
View user's profile Send private message MSN Messenger Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
just do it for 32 bits.
i predict the first retro evolution.
intel will use IA64 as a little extension, making a 32bits µP able to compute 64bits operands.
the address bus will be 32 bits wide, and operands will be 8, 16, 32 & 64.

all the code for native IA 64 long mode will be obsolete.
all native IA64 µP will be abandonned, what a better arch than IA32?
Post 09 Dec 2008, 17:05
View user's profile Send private message Visit poster's website Reply with quote
bogdanontanu



Joined: 07 Jan 2004
Posts: 403
Location: Sol. Earth. Europe. Romania. Bucuresti
bogdanontanu
Quote:

Under 32bit mode its quite common to manage your physical memory into 4k blocks and have a bit in a bitmap specifying if its allocated or not.


No it is not!
Post 09 Dec 2008, 17:14
View user's profile Send private message Visit poster's website Reply with quote
calpol2004



Joined: 16 Dec 2004
Posts: 110
calpol2004
bogdanontanu wrote:
Quote:

Under 32bit mode its quite common to manage your physical memory into 4k blocks and have a bit in a bitmap specifying if its allocated or not.


No it is not!


How then?

This is just a simple easy way of making a simple memory manager for a kernel. Maintain a bitmap of physical 4kb blocks. Whenever you need memory then the memory manager maps a sequence of those blocks to virtual pages and return the pointer to the first.

Some OS's often use structures with extra information as opposed to a single bit. Same principle really.

How else could it be done? blurting out "NO!" is pretty dumb IMO if your not going to tell me why I'm wrong.

I think i am just going to go for the highest amount of memory BIOS interrupt 0x15 will give me. Not sure if int 0x15 will work though, it may only give me regions below 4GB, i haven't heard of any 64bit equivalents so i assume it will.
Post 09 Dec 2008, 17:18
View user's profile Send private message MSN Messenger Reply with quote
Octavio



Joined: 21 Jun 2003
Posts: 366
Location: Spain
Octavio
usually there is free physical memory only when the system boots ,later all the memory is used for aplications of for the disk cache. A simple method is to use linked lists with the available pages.
Post 09 Dec 2008, 18:07
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
calpol2004,

When in doubt, RTFM. Wink

x86-32 can easily address 64 GiBs (36-bit addressing with PAE/PSE-36), x86-64 extends that up to 52 bits (though early CPUs was restricted to 40-bit addressing, for later you must use CPUID to check MAXPHYADDR, maximum physical address width).

Int 15/E820 should be considered with caution. QWORDs for base/length are long enough; you may also examine MTRRs do differentiate that ranges further. Do you think it's only RAM in physical address space?
Post 09 Dec 2008, 19:07
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
edfed,

They already do 64/128 bits (MMX/SSE) Wink
Post 09 Dec 2008, 19:10
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
You will have to deal with "holes" - remember memory mapped devices.

I dunno what the most efficient method of managing memory is, but filesystems are moving away from free-sector bitmaps and towards "extents" - might be worth considering.
Post 09 Dec 2008, 19:33
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
f0dder,

It's direct-mapping vs. list-traversing issue… Not an easy choice without content-addressable (associative) memory.
Post 09 Dec 2008, 19:51
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
i know that, but speak about an extenssion with general purpose registers.
i like a lot this al, ah, eax, ebx, edi, esi representation
my ideal µP for now have this:
al,ah,a2,a3,a4,a5,a6,a7
ax,ay,az,aw
eax,fax
rax

idem for ebx,ecx,edx
and new registers
rex,rfx,rgx,rhx,rix,rjx.. up to 16 64bits registers for general purpose.

index registers:
rsi, rdi
cutted like rax
and 16 index registers in total
rai, rbi, rci, rdi, rei, rfi...

segement registers..? what for?
ok, just because it is usefull, but will be named base registers, and be 32 bits.
ecs= base address of code
eds= base address of data
ees, efs, egs, ehs, eis, ejs, eks, els...
up to 32 registers

it is a dual core µP of course ( cause it is fun.)

the µP will integrate 4Gb of ramonchip.

the pinout will only be for I/O data & address lines, and some very fast communication peripheral
it will send video signal with a vga output pins., up to 1280*1024 32bpp

no need of SSE or any FPU.
i don't care, i just want ot code in asm. and connect it to my electronics for fun.


to know th eoccupation of memory, there is a way.
a file system in the ram, about the ram
Post 09 Dec 2008, 19:54
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
edfed: perhaps you meant to post that in this thread? Razz
Post 09 Dec 2008, 20:11
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
edfed,

How about big bit pool with means to address any portion of it, instead of registers? Well, almost any (regarding ALU size limits). [31…0], [39…32] instead of eax, cl? Shifts will be (almost) free. Wink

Segment/base registers? Addressing modes should be revamped thoroughly to make some use of that, position-independent code (did I said I love PDP-11? Wink)

Multiple cores with integrated memory controller. Cache consistency/memory contention should not be an issue, at least on-chip.

VGA 15-pin D-SUB? HDMI or DisplayPort.

SSE? Why not. FPU? Definitely.

File system in RAM is the VAS descriptors' description. Wink
Post 09 Dec 2008, 20:26
View user's profile Send private message Reply with quote
neville



Joined: 13 Jul 2008
Posts: 507
Location: New Zealand
neville
I don't like the memory bitmap idea because it is the same concept as "file allocation tables" on disks - can lead to fragmentation, performance degradation and the need for defrag.

Much better for the kernel to maintain a Master Memory Contents Database for all processes, and ensure all processes have contiguous memory allocated. The maximum database size can be based on a proportion of available physical memory. 1/128 (~1%) or 1/256 (~0.5%) is about right for FAMOS.

calpol2004, currently X86-64 is limited to 52-bit address bus.

edfed, I like your 8/16/32/64 bit register definitions but it would make the instruction set too big and complex to implement it? Better to add just a few extra "bit-slice" instructions to the instruction set to achieve almost the same result?

_________________
FAMOS - the first memory operating system
Post 09 Dec 2008, 20:51
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
neville,

What is the problem with fragmentation in memory? You don't have to perform costly seeks and wait for plates to rotate in place to read required sector…

Contiguous memory for processes? Let's see…
You have 50% memory load (and uptime is long) and try to allocate 20% of memory. How do you think, probability to have that much contiguous memory will be more than 0.1?
Post 09 Dec 2008, 21:21
View user's profile Send private message Reply with quote
neville



Joined: 13 Jul 2008
Posts: 507
Location: New Zealand
neville
baldr,
Of course memory fragmentation is much less performance degradation than disk fragmentation in a VM OS.

But it is still undesirable. As you have implied yourself - if uptime is long the worse the fragmentation will be! A good OS should run FOREVER with no change in performance, no matter how "busy" it is sometimes.

With memory fragmentation, sooner or later it will be necessary to defrag. Otherwise all available memory will be in e.g. 4K chunks when uptime is very long. So better to "defrag" sooner - at memory allocation time!!! So contigous memory is always allocated initially to the process or data. Actually in practice it is worthwile to allow running processes to grab maybe ONE extra (usually non-contiguous) block of RAM, but "memory bitmaps" are not needed for that!

_________________
FAMOS - the first memory operating system
Post 09 Dec 2008, 22:11
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
neville: with paging and per-process address space, you don't need any kind of "defragmentation".

Is it a problem having the physical memory fragmented in 4kb chunks? Processor cache lines are much smaller than that.
Post 09 Dec 2008, 22:18
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Quote:

Is it a problem having the physical memory fragmented in 4kb chunks? Processor cache lines are much smaller than that.

May cache line associativity be affected by fragmented memory?
Post 09 Dec 2008, 22:54
View user's profile Send private message Reply with quote
neville



Joined: 13 Jul 2008
Posts: 507
Location: New Zealand
neville
f0dder wrote:
neville: with paging and per-process address space, you don't need any kind of "defragmentation".

Is it a problem having the physical memory fragmented in 4kb chunks? Processor cache lines are much smaller than that.

What software mechanisms, if any, are available to control and optimise how the CPU manages its caches? IMO unless EVERYTHING else is fully optimised first it won't make any difference, so who cares? Do you suggest paging the cache too? Wink

With paging and per-process address space you can have pseudo-contiguous logical memory, but it just disguises the actual fragmented physical memory. At the end of the day the CPU has to access physical memory!

So IMO yes, it is a problem. And bit-mapping paged memory is even worse than bit-mapping physical memory.

How big or small should the pages be? 2MB ? 4kB? If you implement paging there are arguments for both, similar to cluster size on disks. Generally the bigger the whole, the bigger the chunk (page, cluster etc) for best "efficiency". But in truth it depends on the nature of the data, which the allocation process has no knowledge of. So the best size is 0. Non-existent!

_________________
FAMOS - the first memory operating system
Post 10 Dec 2008, 00:12
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
neville: as discussed in this thread, not having a paging mechanism poses a lot of problems... like getting your memory fragmented. Allocating big fixed chunks at application startup isn't really a viable solution for typical real-world applications...

Yes, a CPU has to access physical memory, but can you feel a speed difference (on current, real-world x86 hardware) between accessing (physical) pages that are scattered all over RAM vs. physical pages that are allocated contiguously?

On x86, I believe paging is the best solution that's possible, unless we want to go back to win16 style movable memory blocks and lock/unlock-to-get-pointer. And designing an alternative to paging, for a theoretical CPU, is non-trivial.
Post 10 Dec 2008, 01:11
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3042
Location: vpcmipstrm
bitRAKE
A combination of bitmap and linked lists should be used; or a multi-staged bitmap. Say pages are 4kB that is 32kbits - if each bit specifies a 4kB page then each page of memory has flags for 128MB of memory - these pages don't really need to exist unless another bit (higher level bit table) indicates a need to map it. One 4kB page maps 4096GB - if each bit represents 128MB! ...and so on, one 4kB page maps 131072TB - if each bit represents 4TB! etc...

1TB = 2^40, therefore no more than three levels are needed. What are the minimum instructions to access these three levels?

bt [rsi],eax
jnc @F
bt [rsi],ebx
jnc @F
bt [rsi],ecx
jnc @F

Paging should be used unless someone is designing a console type OS.
Post 10 Dec 2008, 02:18
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.