Page 1 of 1
Disk cache for microkernel
Posted: Fri Jun 03, 2005 6:32 am
by Pype.Clicker
(started from a private discussion of BI vs PC)
BI:
Do you plan to incorporate a VFS-Layer?
hm, yep. there will probably be VFS-alike thing. i still have to draw the basis of the main stuff (e.g. how will i set a block cache, and where should i set it ? etc.)
BI:
If you don't feel disturbed by external proposals whilst doing the designing thing, here are some thoughts. Hope I don't bore you.
I'd place the block cache inside the file system service. It fetches blocks from block devices. so it also can keep track of the caching. Also you wouldn't be bothered with transfering block data from device to fs service address space. Althou - there are definitely better approaches (shared memory?)
What about keeping a block cache *per* block device?
If you want to avoid lags in reading and writing operations (especially from stdin/to stdout) when meanwhile disk IO happens, have the fs service spawn a thread per mounted file system. You could also spawn a thread per process - which takes over communication with all the threads of one process. Dunno how good this is.
stay safe
Re:Disk cache for microkernel
Posted: Fri Jun 03, 2005 6:35 am
by Pype.Clicker
Well, the big thing is that i have disk drivers within the microkernel already (which only makes it a "minikernel", somehow). The filesystem service is envisionned for everything that is not "trivially easy", but once the extent list (or a convenient part of it) has been retrieved, i'd like the user process to be able to access disks without additionnal help of the FS service.
This means that i more or less need the disk cache to be consultable from the microkernel aswell and map blocks in the user process if they're cached already, exposing new blocks aswell ...
Re:Disk cache for microkernel
Posted: Fri Jun 03, 2005 7:01 am
by distantvoices
Gonna see ... I have to do some experiments at home ere I can comment on the "map block to user space" point.
I've found it a bit nontrivial to create block mapping for blocks where block.size<4096 and adjacent blocks can belong to different files.
It can be easily done for file systems which store file contents in consecutive manner, i reckon. ISO9660 jumps into mind.
but as said, I have to check this out. til now I do some kind of copying across address spaces. (time intensive)
Btw: Does the user process get the inode info (block list, indir block list, double & triple indir block list) by the fs service so it knows the whereabouts of the file it wants to retrieve from disk? Or do you intend to have the fs service communicate a list of blocks (an array) to the user process so it can retrieve the data on its own? Oh well, I see I'm spoiled by Inode-Filesystems.
Re:Disk cache for microkernel
Posted: Fri Jun 03, 2005 8:23 am
by Pype.Clicker
probably the user program will not receive the inode info. Actually, there are chance the "inode" will not even exists in Clicker filesystems but will instead be replaced by a "metadata stream" (see my rant about
FLUIDS for details)
The FS server would most probably reply with an extents list like "blocks 1234-1244 == file data from 0-10 ; blocks 5678-8765 == file data from 10-<whatever>".
It's then fairly easy to cache that information at kernel level in the client's process and have a tree-based checking "okay, application request to read logical block #8 in file #4 ... that's block 1242 on disk ide0.master"
or "application request logical block #100000, but i don't have that right here ... just forwarding the request to the FS service and see what it thinks about it."
Re:Disk cache for microkernel
Posted: Wed Jun 08, 2005 1:27 am
by distantvoices
you might place the block cache in kernel level - there where the drivers are located. It might be (for HD's) even a block cache per partition. That#d be cool. the driver just forwards the fetched data (either from disk or cache) to the requestor - and the fs service has nothing to do with it.
The "extents list" as a table to give relation between disk block and offset into file is definitely a good idea.
say: 0:4096=23:24;45:46;56:59
where the left side stands for the offset-range into the file and the right side stands for the blocks which cover this address range.
one 'd also need a means to have (as you say) the driver ask the fs service "hey, that program requests offset 4567 from the file, gimme the blocknumber to fetch", because it#s task of the fs to decipher offset into file to Block to fetch.
It might also be possible to tell the driver the size of the file so that it can tell EOF as soon as the user process has read the whole file.
regarding the FLUID-Document: that's quite interresting stuff. I think it might be worth a buncha thoughts about FLUIDS and pipes. I for one would keep some pool of temporary FLUIDS to deal out to pipes (the anonymos ones).
BTW: The inode is just something for fs service internal. The user process just needs the global descriptor of the file - the FLUID, which builds up the relation between fs node and user process. So, more than one process can open one file. They just get the same FLUID, is that right?
Then, Locking ... (to be extended later, ere I cross the max post content *rofl*)
<rant>
As for Pipes...
The unixy approach to do an anonymous pipe is: create a pipe with pipe(&fd)?! call. then fork off the process which is to take the other end. then close my unneeded part of the pipe (either the read only or the write only end - the other process does the opposite of me) and then the operations might start. That works because fork passes all the file descriptors the forking process has.
I'd prefer the pipe be just one fd, bidirectional, so that information can be passed in either directions. It 'd just require a mechanism to prevent the two processes to write to the pipe at the same time. Just this: a writes, b reads. b writes, a reads. as simple as this. There should go a return code to the other process in case it tries such a write.
/dev/brain > /dev/null ... *ramblerumbleramble*
</rant>
more to come ... /dev/brain is still rambling ...
Re:Disk cache for microkernel
Posted: Sun Jun 12, 2005 4:51 am
by Pype.Clicker
since i'll try to avoid the obsolete unix kludge of fork+exec (e.g. applications will have the opportunity of running in "winter" mode where they'll consume minimal resource but still allow other programs to contact them, enumerating available communication streams, asking for "app://help" stream and things alike, i don't worry too much about the way pipes will be opened.
It will probably look more like "Stream str=connect("FuturePlayer:VolumeControl")" scheme.
That means streams and files will not use the same backend, and among other things, they will not be storable in the FS (which means they'll need no FLUIDs).
What will be more a concern is - for instance - streams within streams. E.g. with the current design, i don't exactly know what to do if i want to get a FLUID for a file in a ZIP archive. Probably i'll have to store a couple of <base fluid, key for that fluid's offset> ... Or maybe i could manage to have "derivative FLUIDs" that would contain the fact that they're offset of another FLUID, e.g.
archive.zip == 12345678900000000
archive.zip/ == 12345678900000010
none of those scheme really please me, though ...
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 1:41 am
by Candy
beyond infinity wrote:
As for Pipes...
The unixy approach to do an anonymous pipe is: create a pipe with pipe(&fd)?! call. then fork off the process which is to take the other end. then close my unneeded part of the pipe (either the read only or the write only end - the other process does the opposite of me) and then the operations might start. That works because fork passes all the file descriptors the forking process has.
I'd prefer the pipe be just one fd, bidirectional, so that information can be passed in either directions. It 'd just require a mechanism to prevent the two processes to write to the pipe at the same time. Just this: a writes, b reads. b writes, a reads. as simple as this. There should go a return code to the other process in case it tries such a write.
That gives the same problem as in Unix, which is why they're split. If you have bidi access points, you can write and read from one end, so you can NEVER get an eof. No EOFs prevents the use of single-way data streams with implicit end, which is the main use for pipes.
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 3:31 am
by distantvoices
@candy:
well, it deserves me right to be told an olden babel talker for writing ere thinking it completely to the end. man, I've completely forgotten about the close(fd) thing.
What i do not get is the "implicit end".
A Pipe connection exists as long as one process writes and the other reads (where reading is a blocking call and writing without someone reading at the other end causes a SIGPIPE signal coz of broken pipe).
Isn't the writer supposed to write EOF to the pipe as soon as it terminates it's part of the operation?
Or does the pipe layer generate EOF as a result of the writer closing its part of the connection?
@Pype: for the block cache ... we always think about caching *blocks*
Why don't we cache *files* and store their contents in a contiguous area(page arrays or so which cover the size of the file)? this would make memory mapped files a breeze f. ex. Or better: memory mapped executables?
What about this approach? Complete rubbish?
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 6:12 am
by Candy
beyond infinity wrote:
What i do not get is the "implicit end".
A Pipe connection exists as long as one process writes and the other reads (where reading is a blocking call and writing without someone reading at the other end causes a SIGPIPE signal coz of broken pipe).
Isn't the writer supposed to write EOF to the pipe as soon as it terminates it's part of the operation?
Or does the pipe layer generate EOF as a result of the writer closing its part of the connection?
The latter.
@Pype: for the block cache ... we always think about caching *blocks*
Why don't we cache *files* and store their contents in a contiguous area(page arrays or so which cover the size of the file)? this would make memory mapped files a breeze f. ex. Or better: memory mapped executables?
What about this approach? Complete rubbish?
Sorry if I wasn't supposed to reply
Memory mapped executables is pretty standard in caching. You assure that the executable can't be physically deleted or changed (unlinked, but not removed) while it's running and you can keep using it. Memory mapping files is up to a certain limit possible. Imagine somebody comparing a bunch of corefiles, each of a (for memory mapping purposes) 4GB in size. That's hard to fit in 2GB of user space. Inversely, the same for 64-bit mode in which it's equally impossible. It's unpractical. However, it would be a nice idea if you could link the block to a file, so that it will be unmapped first when the file is closed, instead of a different block that's still in use.
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 6:51 am
by AR
Windows supports memory mapping files larger than the user address space (2GB) by creating a mapped "window" of the file, say a contiguous block of 1024 virtual pages, when you finish with that section you can issue a 'remap' call to move the window somewhere else in the file (The data is only physically loaded into memory when the program page faults in the window - although the block caching service may preload it).
I expect file memory mapping will be more common in 64bit software since the address space is so impossibly huge (If one program used the whole of it's 18 exabyte address space you'd probably have run out of paging file a long time before that) a simple way to benefit at least until terabyte RAM sticks is to memory map instead of fread-ing. (What files do you know of that are 2^64 in size, Candy?

)
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 7:35 am
by Candy
AR wrote:
Windows supports memory mapping files larger than the user address space (2GB) by creating a mapped "window" of the file, say a contiguous block of 1024 virtual pages, when you finish with that section you can issue a 'remap' call to move the window somewhere else in the file (The data is only physically loaded into memory when the program page faults in the window - although the block caching service may preload it).
I expect file memory mapping will be more common in 64bit software since the address space is so impossibly huge (If one program used the whole of it's 18 exabyte address space you'd probably have run out of paging file a long time before that) a simple way to benefit at least until terabyte RAM sticks is to memory map instead of fread-ing. (What files do you know of that are 2^64 in size, Candy?

)
To answer the end first, a core dump of a process having a number of memory mapped files open of course. Core dumps always grow to be exactly the entire memory size and you can't shrink them. It's the classical N = N+1 problem, you need to keep the entire core file in memory, plus the debugger. Both have the same limit, yet the debugger is not nothing, so it doesn't fit with the theoretical maximum core file.
Other than that, I can't think of much that would reasonably fill that without loads of redundancy. Maybe a 3d transview of the world in 2m increments or a compressed full universe overview... Or the original Hitchhikers Guide to the Galaxy...
To make it an inverse thing, put yourself in the 1980s or 1970s and consider what sort of an idiotic file you'd need to fill 4 entire gigabytes. You wouldn't be able to comprehend, same as we can now not comprehend 16 exabyte. In 30 years time, if you use it for memory mapping all files, you will be laughed at very hard.
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 8:01 am
by Brendan
Hi,
Just a minor correction of a common misconception...
Current 64 bit CPUs do not support 64 bit virtual address or 64 bit physical address.
The 64 bit extension supports an implementation defined number of virtual address bits (between 32 and 64), and an implementation defined number of physical address bits (between 32 and 56).
For example, Intel's first 64 bit CPU only supports 40 bit linear addresses and 36 bit physical addresses, while AMD's 'Hammer' only supports 48 bit virtual addresses and 40 bit physical addresses. Over time CPU manufacturers will increase the number of supported bits...
Due to the way the virtual address space is split in half when less than 64 bits is implemented, I expect that all 64 bit OSs will use one half for CPL=0 and the other half for CPL=3 (otherwise there'd be a huge gap in the middle of CPL=3 space). Therefore, with current 64 bit CPUs you could end up with only 512 GB (2^39 bytes) of virtual address space for CPL=3 code (on an Intel CPU).
It's taken Intel 20 years to go from 32 bit to 40 bit (total virtual address space size). This works out to an average of 1 virtual address bit every 30 months, so those other 24 virtual address bits may take another 720 months (or 60 years). If I'm lucky I'll be in an old folks home before then.
Cheers,
Brendan
Re:Disk cache for microkernel
Posted: Mon Jun 13, 2005 9:05 am
by AR
Hopefully the debugger would only memory dump the actually used portions and would disregard memory mapped files which would drastically reduce the size.
The key-phrase there is "in 30 years time", this isn't 30-years time, this is now, and in the now memory mapping is about the only way you are going to benefit. 1TB harddrives are probably about 2 years away at least, and the rate at which RAM gets larger then becomes affordable is slow. It is highly unlikely that software I wrote now would be used in 30-years time, and if it was then people would expect it to not take full advantage of their system anyway (You don't expect a DOS game to take full advantage of your brand new Geforce 6800GT but people still play them occasionally), if it's Open Source then chances are that someone would 'fix' it when we actually get to that point anyway.
(I am aware that the address space isn't actually 64bits yet but that is the maximum limit until 128bit CPUs which is what I was working off)
Re:Disk cache for microkernel
Posted: Fri Jun 24, 2005 6:13 am
by Pype.Clicker
beyond infinity wrote:
@Pype: for the block cache ... we always think about caching *blocks*
Why don't we cache *files* and store their contents in a contiguous area(page arrays or so which cover the size of the file)? this would make memory mapped files a breeze f. ex. Or better: memory mapped executables?
What about this approach? Complete rubbish?
Well, the problem is that you don't have only files. Inodes, indirect blocks, directories, bitmaps, etc. also need to be cached (okay, in a microkernel approach, that'd rather be the job of the fileserver).
I suppose the reason why we have _blocks_ caches instead of _files_ cache is that we usually read/write files in a 'per-block' fashion. It makes no sense to cache a whole audio/video stream, for instance, since you're likely to need each block only once (even if you're adjusting volume), so if you need more blocks for something else, you're free to use them.
Moreover, it's much more efficient to have a cache of constant-sized entries rather than variable-sized entries as you can easily trash any of those entries to host any newer entry.