|
1 Introduction 2 Ground Rules Building a File System 3 File Systems 4 File Content Data Structure 5 Allocation Cluster Manager 6 Exceptions and Emancipation 7 Base Classes, Testing, and More 8 File Meta Data 9 Native File Class 10 Our File System 11 Allocation Table 12 File System Support Code 13 Initializing the File System 14 Contiguous Files 15 Rebuilding the File System 16 Native File System Support Methods 17 Lookups, Wildcards, and Unicode, Oh My 18 Finishing the File System Class The Init Program 19 Hardware Abstraction and UOS Architecture 20 Init Command Mode 21 Using Our File System 22 Hardware and Device Lists 23 Fun with Stores: Partitions 24 Fun with Stores: RAID 25 Fun with Stores: RAM Disks 26 Init wrap-up The Executive 27 Overview of The Executive 28 Starting the Kernel 29 The Kernel 30 Making a Store Bootable 31 The MMC 32 The HMC 33 Loading the components 34 Using the File Processor 35 Symbols and the SSC 36 The File Processor and Device Management 37 The File Processor and File System Management 38 Finishing Executive Startup Users and Security 39 Introduction to Users and Security 40 More Fun With Stores: File Heaps 41 File Heaps, part 2 42 SysUAF 43 TUser 44 SysUAF API Terminal I/O 45 Shells and UCL 46 UOS API, the Application Side 47 UOS API, the Executive Side 48 I/O Devices 49 Streams 50 Terminal Output Filters 51 The TTerminal Class 52 Handles 53 Putting it All Together 54 Getting Terminal Input 55 QIO 56 Cooking Terminal Input 57 Putting it all together, part 2 58 Quotas and I/O UCL 59 UCL Basics 60 Symbol Substitution 61 Command execution 62 Command execution, part 2 63 Command Abbreviation 64 ASTs 65 Expressions, Part 1 66 Expressions, Part 2: Support code 67 Expressions, part 3: Parsing 68 SYS_GETJPIW and SYS_TRNLNM 69 Expressions, part 4: Evaluation UCL Lexical Functions 70 PROCESS_SCAN 71 PROCESS_SCAN, Part 2 72 TProcess updates 73 Unicode revisted 74 Lexical functions: F$CONTEXT 75 Lexical functions: F$PID 76 Lexical Functions: F$CUNITS 77 Lexical Functions: F$CVSI and F$CVUI 78 UOS Date and Time Formatting 79 Lexical Functions: F$CVTIME 80 LIB_CVTIME 81 Date/Time Contexts 82 SYS_GETTIM, LIB_Get_Timestamp, SYS_ASCTIM, and LIB_SYS_ASCTIM 83 Lexical Functions: F$DELTA_TIME 84 Lexical functions: F$DEVICE 85 SYS_DEVICE_SCAN 86 Lexical functions: F$DIRECTORY 87 Lexical functions: F$EDIT and F$ELEMENT 88 Lexical functions: F$ENVIRONMENT 89 SYS_GETUAI 90 Lexical functions: F$EXTRACT and F$IDENTIFIER 91 LIB_FAO and LIB_FAOL 92 LIB_FAO and LIB_FAOL, part 2 93 Lexical functions: F$FAO 94 File Processing Structures 95 Lexical functions: F$FILE_ATTRIBUTES 96 SYS_DISPLAY 97 Lexical functions: F$GETDVI 98 Parse_GetDVI 99 GetDVI 100 GetDVI, part 2 101 GetDVI, part 3 102 Lexical functions: F$GETJPI 103 GETJPI 104 Lexical functions: F$GETSYI 105 GETSYI 106 Lexical functions: F$INTEGER, F$LENGTH, F$LOCATE, and F$MATCH_WILD 107 Lexical function: F$PARSE 108 FILESCAN 109 SYS_PARSE 110 Lexical Functions: F$MODE, F$PRIVILEGE, and F$PROCESS 111 File Lookup Service 112 Lexical Functions: F$SEARCH 113 SYS_SEARCH 114 F$SETPRV and SYS_SETPRV 115 Lexical Functions: F$STRING, F$TIME, and F$TYPE 116 More on symbols 117 Lexical Functions: F$TRNLNM 118 SYS_TRNLNM, Part 2 119 Lexical functions: F$UNIQUE, F$USER, and F$VERIFY 120 Lexical functions: F$MESSAGE 121 TUOS_File_Wrapper 122 OPEN, CLOSE, and READ system services UCL Commands 123 WRITE 124 Symbol assignment 125 The @ command 126 @ and EXIT 127 CRELNT system service 128 DELLNT system service 129 IF...THEN...ELSE 130 Comments, labels, and GOTO 131 GOSUB and RETURN 132 CALL, SUBROUTINE, and ENDSUBROUTINE 133 ON, SET {NO}ON, and error handling 134 INQUIRE 135 SYS_WRITE Service 136 OPEN 137 CLOSE 138 DELLNM system service 139 READ 140 Command Recall 141 RECALL 142 RUN 143 LIB_RUN 144 The Data Stream Interface 145 Preparing for execution 146 EOJ and LOGOUT 147 SYS_DELPROC and LIB_GET_FOREIGN CUSPs and utilities 148 The I/O Queue 149 Timers 150 Logging in, part one 151 Logging in, part 2 152 System configuration 153 SET NODE utility 154 UUI 155 SETTERM utility 156 SETTERM utility, part 2 157 SETTERM utility, part 3 158 AUTHORIZE utility 159 AUTHORIZE utility, UI 160 AUTHORIZE utility, Access Restrictions 161 AUTHORIZE utility, Part 4 162 AUTHORIZE utility, Reporting 163 AUTHORIZE utility, Part 6 164 Authentication 165 Hashlib 166 Authenticate, Part 7 167 Logging in, part 3 168 DAY_OF_WEEK, CVT_FROM_INTERNAL_TIME, and SPAWN 169 DAY_OF_WEEK and CVT_FROM_INTERNAL_TIME 170 LIB_SPAWN 171 CREPRC 172 CREPRC, Part 2 173 COPY 174 COPY, part 2 175 COPY, part 3 176 COPY, part 4 177 LIB_Get_Default_File_Protection and LIB_Substitute_Wildcards 178 CREATESTREAM, STREAMNAME, and Set_Contiguous 179 Help Files 180 LBR Services 181 LBR Services, Part 2 182 LIBRARY utility 183 LIBRARY utility, Part 2 184 FS Services 185 FS Services, Part 2 186 Implementing Help 187 HELP 188 HELP, Part 2 189 DMG_Get_Key and LIB_Put_Formatted_Output 190 LIBRARY utility, Part 3 191 Shutting Down UOS 192 SHUTDOWN 193 WAIT 194 SETIMR 195 WAITFR and Scheduling 196 REPLY, OPCOM, and Mailboxes 197 REPLY utility 198 Mailboxes 199 BRKTHRU 200 OPCOM 201 Mailbox Services 202 Mailboxes, Part 2 203 DEFINE 204 CRELNM 205 DISABLE 206 STOP 207 OPCCRASH and SHUTDOWN 208 APPEND Glossary/Index Downloads |
The HMC Loading the HMC The HMC manages the heap for the executive. Why do we need a heap manager component if we already have a memory management component? Can't we combine them into a single component? Well, yes, they both have to do with managing memory, but they perform radically different operations. The MMC provides an abstraction of physical memory pages. The HMC allocates and deallocates arbitrary chunks of memory - asking the MMC for pages of memory and then suballocating from that. The HMC The design for our component is to respond to allocation requests by asking the MMC for memory, from which we allocate what was requested. Each chunk of memory requested from the MMC is managed as its own sub-heap. When we get a request, we allocate from one of our sub-heaps. We only ask the MMC for more memory if the request cannot be met with the free memory in any of our sub-heaps. Within each sub-heap, we allocate via an allocation table, as opposed to the chained buffers used in the temporary heap. This is both faster and reduces the chances of fragmentation considerably. But it requires more complicated code than the simple heap. Here is our Sub_Heap and HMC class definitions: The sub-heaps have a starting position in memory, a size (in bytes), and an allocation table. The first thing you might note in the HMC are the metrics, such as _Allocation_Count. These values are counts that are incremented as the HMC runs, allowing us a means of measuring various things, such as the peak amount of allocated memory, which may indicate to us how well we clean up unused memory in the executive. Another is the number of sub-heaps, which may indicate how fragmented the heap has become. We will look at how to use these in a future article. Here are the functions to access the metrics. The last method provides the only means of setting the metrics from outside the class. It is used to reset the counters. The purpose of such a reset is to measure metrics from a given point, such as when changing some setting that might affect heap management/usage. This way the heap usage can be measured from the point of the change. Here are the utility routines and constructor for our class: Like the MMC, we have a startup flag in the HMC, and setting it is the only thing we do in the constructor. The Sub_Heaps function serves up a list of the sub-heaps, and we defer the creation of the list until it is referenced. The other methods are self-explanatory. Once we are set up, all executive memory requests, including our own, come to us. To make sure our own requests come to us, we set the Delphi memory manager. The following routines handle this. The End_Startup function, like its equivalent in the MMC, clears the Startup flag. It also links us to the memory manager, and calls Start_Subheap to initialize the first sub-heap, if it isn't already set up. The only questionable line in the routine is setting the _Heap variable from the Kernel heap rather than setting it to ourselves. This is to support the case when the HMC is hot-swapped after UOS starts up. We will discuss hot-swapping executive components in the future. And here is the Start_Subheap method: The SubHeap instance variable is used to hold the first sub-heap that we need, before the list of subheaps is created. We ask the MMC for a chunk of memory that the subheap will point to. We default the size of this chunk to 4Kb, but the MMC may allocate something larger due to page sizes. S (the size) is passed by reference so that the MMC can change it to the actual allocation amount. We then set the sub-heap's size and pointer. We don't create or assign an allocation table, because that would require an allocation. So long as we are in startup mode, any memory requests we get are allocated out of that sub-heap. Shortly, we will see how we manage allocations in this sub-heap without an allocation table. Now let's look at the method that allocates memory in the heap, Getmem: First we save the requested size, then we add the size of an integer to the requested size. Like the temporary heap, the HMC stores the size of the chunk just prior to the pointer that we return. Next, we check to see if we are in startup mode or if we are recursed within another call to Getmem. On some occasions, Getmem needs to allocate memory (such as another subheap). Without this check, such a situation would result in an infinite recursion that would blow the stack. In either case, we want to allocate from our initial sub-heap. The first thing to do is check to see if the initial sub-heap has been allocated. If not, we call the Start_Subheap method that we discussed above. We set the a temporary result that points to the first free byte in the sub-heap. The Preallocated instance variable is used as a high-water mark to indicate how much of the initial sub-heap has been used. We never make this value less - only more. This saves us from needing an allocation table for the initial sub-heap, but it also prevents us from reusing any of the memory associated with the sub-heap. Requests to free memory in this sub-heap can be made, but the Preallocated variable means that it can never be reused for another allocation request. If the requested size is more than remains in the sub-heap, we return nil. This is probably a fatal error if it occurs. Next we increment the allocation, and the number of bytes allocated, counters. Finally, we store the chunk size, and then return a pointer to the chunk just following this size value. Note that, unlike the temporary heap (or the following code), we do not round the requested size up at all. This means that our allocation resolution is 1 byte, with a minimum allocation of five bytes on a 32-bit system. Because we do not reuse memory in the initial sub-heap, we are not worried about memory fragmentation here. Also, because this is a limited resource that will likely crash the executive if it is exhausted, we don't want to waste even one byte on overhead. The remaining code in this method deals with the case when we are not in startup mode. In the case when we're not in startup mode, we first round the requested size (plus integer size) up to a multiple of 16 bytes. Then we see if the _Sub_Heaps list has been instantiated. If not, we create the list. However, before we do that, we set the In_Getmem flag. The call to TList.Create will, in turn, recursively call Getmem. Setting this flag ensures that we go through the startup code (described above) which will allocate from our initial sub-heap. After the list creation, we clear the flag. That means that this block of code is only executed once, since we never set _Sub_Heaps to nil. At this point, the HMC instance is fully set up, and we are ready to do the requested allocation.
This loop goes through all of the subheaps, looking for one that has enough contiguous free space to fulfill the requested size. The first line of the loop is not just for shorthand - it also reduces some overhead. We request the allocation from the current sub-heap. If the request returns nil, we continue on to the next sub-heap in the list. If successful, we copy the size value to the lowest address. The address we use is the returned value added to the sub-heap start because the allocation table returns a 0-based offset into the buffer that starts at the sub-heap Start pointer's address. This results in an actual memory address. Then we update the various counters and return the address to the caller.
If we get to this point, there were no sub-heaps with sufficient free space. So, we call the local Allocate function to create another sub-heap to allocate from. Kernel_Heap_Incremental_Allocation defines the minimum amount to allocate for a sub-heap when we need to expand the heap. This is currently defaulted to 4Kb. First we see if the amount being requested is greater than this default. We will try to create a sub-heap of a size that is the greater of the two values. If the allocation is successful, we recursively call ourselves to do the actual allocation (whose size was saved in Original). In_Getmem is set before calling Allocate, and cleared afterwards. This is to ensure that any new memory allocations that happen during the Allocate call are met from the initial sub-heap. Otherwise, such an allocation could result in an infinite loop if there is no available space in any of the sub-heaps for whatever the Allocate function requests. Here is the Allocate function: If the initial sub-heap isn't set up yet (SubHeap.Start is nil), we call the Start_Subheap. After this, if it still isn't set up or the size is 0, we halt with an error. This is an unrecoverable error - the executive needs to allocate memory and there is no memory to allocate.
Besides the memory that we are allocating on behalf of the calling code, we need to allocate memory for the TSub_Heap instance itself. The Max_Currently_Available function returns the maximum size of a memory allocation from our current set of sub-heaps. If there is room in our current set of sub-heaps, we will allocate the TSub_Heap instance from that. Otherwise, we need to include it in the memory that we will request from the MMC. In the latter case, we increase the supplemented size by the size of a TSub_Heap instance (SSize). In either case, we add 16 to the size. This is to compensate for the first allocation bit in the allocation table, which is always set, thus giving us 16 bytes less than (1 bit maps 16 bytes) than the total memory mapped by the allocation table. If we can allocate the memory for the new sub-heap from the existing sub-heaps, we call getmem to do so. In theory, if Max_Currently_Available says there is room, there should be no way for getmem to return nil. But we check anyway, just to be safe.
Next, we make sure that we are not allocated less than the minimum allocation (the Min parameter). Next, we request the memory from the MMC. If this fails, it will be because there isn't sufficient physical RAM available to supply our request. In such a case, we will try just allocating what the calling code requested, plus the 16 bytes for the first allocation bit (see above discussion). If even this fails, we will try to allocate just the requested amount. One would expect that this would fail to meet the needs of the calling code, and one would be correct with the current allocation table implementation. But this code is there for the eventual change in the allocation table implementation that won't automatically lose the first bit of allocation. But, if even that fails, we exit with a False result - meaning that the allocation failed.
Next, we assume that we will succeed, and set our result to True. If we allocated the new sub-heap in the memory we requested from the MMC (Include_Subheap is true), then we point the sub-heap to the starting address of the memory chunk. We set the sub-heap's size, and set the size prefix if the include_subheap is true.
if( Max_Currently_Available < Size_Needed( sizeof( TAT64 ) ) ) then
begin
In_Getmem := True ;
end ;
S.AT := TAT64.Create( 16 ) ;
In_Getmem := False ;
Bytes := S.Size div 16 div 8 ;
if( Max_Currently_Available < Size_Needed( Bytes ) ) then
begin
In_Getmem := True ;
end ;
S.AT.Set_Size( Bytes ) ; // Allocation table size = 8 bits per byte x 16 bytes per bit
In_Getmem := False ;
S.AT.Allocate_At( SSize, Bytes * 16 * 8 - SSize ) ;
// Make sure extra allocation bits are set if Size not on a 8*16 byte boundary
if( SSize > Size ) then // If space for subheap was included in the allocation
begin
In_Getmem := True ;
S.AT.Allocate( sizeof( TSub_Heap ) + sizeof( pointer ) - 16 ) ;
{ Mark subheap record as allocated memory (-16 because subheap starts in
reserved first allocation block) }
In_Getmem := False ;
_Current_Allocation := _Current_Allocation + sizeof( TSub_Heap ) - 16 ;
if( _Current_Allocation > _Peak_Allocation ) then
begin
_Peak_Allocation := _Current_Allocation ;
end ;
end ; // if( SSize > Size )
In_Getmem := True ;
Sub_Heaps.Add( S ) ;
In_Getmem := False ;
end ; // THMC.Getmem.Allocate
Next we create the allocation table, and set its size based on the size of the memory we got from the MMC. Note that if Max_Currently_Available indicates that there isn't sufficient heap space to hold the allocation table instance, we set the In_Getmem flag so that it is allocated from the initial heap. We do something similar when we call AT.Set_Size. This function will allocate heap memory to hold the allocation table, which will be the size of the number of bytes that we pass. If this can be allocated from the general heap, we don't need to set the In_Getmem flag. Otherwise, it is allocated from the initial sub-heap. Next, we make sure that any bits in the allocation table beyond those mapping our buffer are set. The reason for this is because the AT represents the total allocatable area in 8-bit bytes. Each bit matches our minimum heap allocation size of 16 bytes. Thus, each byte in the allocation table maps 128 bytes. But if the MMC returns a value that is not an exact multiple of 128 bytes, some of the bits in the last byte of the allocation table map to addresses outside of our memory chunk. As an example, let's say that the MMC returned a page of memory that was 192 bytes long. That requires 12 bits in the allocation table. However, the allocation table has to allocate in 8-bit chunks, meaning it needs 16 bits to map the 192 byte page. But the last 4 bits map byte offsets 192-255, which are not in the page that the MMC returns to us. If the allocation table ever were to use those bits on an allocation request, it would return addresses that are not in the page that we are using. Use of the returned address could result in any number of possible results - none of them good. In such a case, we make sure those last 4 bits are set, so that the allocation table never thinks they represent available space. In reality, it is unlikely that UOS will run on any system that allocates less than 256-byte pages, so this precaution may never be needed. However, we must try to avoid making assumptions about the hardware we are running on. To set the bits in the allocation table, we simply request an allocation of the appropriate size at the appropriate address. The allocation table will mark those bits as used. If the new sub-heap was allocated within its own memory, we need to mark that as allocated as well. Otherwise, our first allocation request to the allocation table will point to the memory being occupied by the sub-heap data. Overwriting that with heap data would almost certainly make the executive die. Then we update the various metric data. Finally, we have our new sub-heap set up and we add it to the Sub_Heaps list. However, we must set In_Getmem to true before doing this, or any memory allocation resulting from this operation will like use memory from our new sub-heap, which might make the available space less that what was needed for the original request which set off this chain of events. So, we force the Sub_Heaps list data to be allocated from the initial sub-heap. Then we clear the flag and the function is done. The calling code will then make the allocation call, which will come from our newly created sub-heap. Whew! There's a lot of potential work that needs to be done when allocating heap in the executive. Fortunately, the remaning HMC methods are much simpler. Here is the Free method. If the _Sub_Heaps list is nil, there are no sub-heaps and, thus, nothing we can deallocate. A call to this method in that case may be the result of deallocating something in the initial sub-heap. As mentioned earlier, allocations in the initial sub-heap are permanent. Otherwise, we iterate through the sub-heaps in the list. For each sub-heap, we see if the passed pointer is within the sub-heap's memory. If not, we continue on to the next sub-heap. If so, we grab the size prefix and deallocate the range from the allocation table. Then we update the metrics and exit. Here is the Realloc method. If the passed pointer is nil, then we are not reallocating, since we don't allow anything to be allocated at address 0. So, we treat it as a straight allocation, and just call Getmem and return. Otherwise, we get the size prefix address via the Get_Size_Header function, round the new size up to a multiple of 16 bytes, and then compare the current and new sizes to see if the request would actually result in a difference in the amount of allocated memory. If not, we simply return the current pointer - this is a logical resize-in-place, with no change in physical allocation. The basic operation is to try to reallocate in-place or, failing that, to reallocate within the same sub-heap or, failing that, to reallocate in any sub-heap that has space for the new allocation (in the worst case scenario, a new sub-heap will be created to meet the memory demand). These represent the fastest to slowest means of responding to the request. As to the actual code - we loop through the sub-heaps, to find the one which corresponds to the passed pointer. Once we find the matching sub-heap, we try to extend the allocation in the allocation table. If that fails (Destination is 0), We try to allocate a buffer of the new size within this sub-heap. If that also fails, we then request a new buffer from Getmem. If that also fails, we set the In_Getmem flag and call Getmem - in effect trying to allocate from the initial heap. If we get here, it means we are desperate and it is better to use more of the initial heap than to fail to allocate memory for the executive. If we succeed, we copy the data from the old location to the new one. We have to make sure that the amount copied is the lesser of the existing or new size. Otherwise we might overwrite some other data or even access non-existant memory. Next we free the old allocation and exit. If we couldn't reallocate in-place, we copy the data from the old location to the new. Then we update metrics. Finally, we update the size prefix and set the return value to the destination pointer. If the destination pointer is different than the original pointer (P), it means we moved the data and so we free the original pointer. If we make it down to the following code, it means we didn't find the source pointer in any of the sub-heaps (it might be from the initial heap, or maybe from some memory directly allocated from the MMC). This means that we are not responsible for managing the memory pointed to by the passed pointer. In this case, all we can do is allocate the new buffer via Getmem. If that fails, we exit (returning a nil pointer). Otherwise, we determine how much to copy and move the contents from the old to the new buffer. The old memory isn't deallocated, but there is nothing we can do about that. Here is the code for the Get_Size_Header function: It simply returns a pointer that is one integer worth of bytes less than the passed pointer. Thus, it points to the beginning of the size prefix for the passed pointer. Now that we have the main methods of Getmem, Free, and Realloc taken care of, we turn our attention to the MaxAvailable method. This method returns the size of the single largest allocatable chunk of memory. This includes what is potentially available from the MMC. We accomplish this by looping through the sub-heaps and looking at the allocation tables' MaxSpace. If _Sub_Heaps is nil, we are not yet set up. So, we simply return the remaining space in the initial sub-heap and exit. Otherwise, we take the maximum size we found and subtract the size of the size prefix and round down to the nearest 16 bytes. Finally, we see how large a chunk of memory we could get from the MMC. If that is larger than the largest space we've found so far, we return it instead. A similar method is MemAvailable: This method does the same thing as MaxAvailable except that it adds up all available (and potential) heap space. Finally, the Max_Currently_Available method: This method is almost exactly the same as the MaxAvailable method except that it doesn't include potential space from the MMC, or from the initial sub-heap. In the next article, we will discuss loading the other executive components. |