JPH10198587A - Indirect addressing method/device for file system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To optimize indirect addressing by giving a first pointer entry to a file by a file control block. SOLUTION: When a point data indicator is in a first state, pointers 28A, 30A and 32A are connected with a logic address and a physical address is set. When the pointer data indicator is in a second state, the logic address is divided into an index and offset and the logic address is updated to offset. When the pointer data indicator is in the second state, a next pointer entry is pulled out from a position in indirect blocks 14, 16, 18, 22, 24 and 26 instructed by the present pointers and the designated indirect address block instructed by the index. A conversion process is to connect the physical address and the logic address, and the step is repeated until the physical address is set.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to indirect addressing of files in a file system.
More particularly, the present invention relates to improving indirect addressing with additional control information.

[0002]

BACKGROUND OF THE INVENTION To a user or application program, a file is viewed as a contiguous area of disk space addressed from byte 0 to one less than the file size. In practice, such files can contain various physical data files spread across the disk.
Stored as a block. Therefore, to translate the file offset provided by the application to a physical address in the data storage, some address translation method is required.

[0003] A very common translation method uses a tree of fixed size indirect address blocks. One example of this conversion method is the Unix File System (UFS:
Unix File System). An indirect address block is a block of metadata, including an array of block pointers. These block pointers point to other lower level indirect address blocks. At the lowest level of metadata, the indirect address block points to a fixed size data block. The control block for a file, which is an I-node in Unix, points to the highest level indirect address block.

[0004] The translation method begins by using the high order bits of the offset as an index into the root indirect address block. In the root indirect address block, a pointer to the second level indirect address block is derived. Next, the pointer to the third level indirect address block is fetched using the next higher bit of the offset as an index in the second level indirect address block.
Again, the next higher bit of the offset is used to find the pointer in the third level indirect address block. This pointer may point to yet another indirect address block, or may point to a data block. With the pointer from the last indirect address block, it is the least significant set of offset bits that is used as the byte index to find the data in the data block.

[0005] The tree of indirect address blocks that ultimately result in data blocks has a fixed depth.
Having. For example, to support a 32-bit (4 gigabyte) file system with 4 kilobyte indirect address blocks and 4 kilobyte data blocks (traditional Unix file system),
Two levels of indirect address blocks are required. Each level is 10 bits (1024 4-byte blocks)
Pointer), and the data block uses 12 bits. In a file system with a 63-bit file, using an 8 kilobyte indirect address block with an 8 kilobyte data block,
There are five levels of indirect addressing, each level will have 10 bits, and the data block will have 13 bits.

The problem with this indirect addressing approach is that it uses a very large amount of disk space and memory for the metadata and spends a significant amount of time processing the metadata to obtain the file. For example, each data
A block (typically 8 kilobytes on Unix) is associated with an 8-byte entry in the lowest level indirect address block. One terabyte of file requires some more than one gigabyte of indirect address block storage. This is a very large amount of metadata to manage. Since many of the files stored in the large file system are adjacent files, it can be seen that much of the indirect addressing of this meta data is wasted space.

[0007] The indirect addressing file system assumes that the file data blocks are distributed throughout the file system or at least over a number of small contiguous areas. However,
Many application programs seek to store necessary files in contiguous space in the file system to increase the efficiency and speed of operation. as a result,
The block at the indirect address is a continuous array of pointers (sequent
Often it has an ial arrangement. A contiguous array of pointers means that each indirect address block points to the next adjacent data block. One solution in such a situation is to increase the size of the data block. However, the larger the size of the data block, the smaller the file. A large amount of storage space is wasted because the file does not fill up the data blocks.
On average, half of the last block remains unused, even if the file is large, provided that the file size is randomly distributed.

In order to solve the problem of making large blocks of metadata compatible with waste of data block space in a file system, "extent" is used.
s) ". In the "extent" file system, each file is defined by a list of physical addresses, with the length of each block at each physical address. For example, a file with non-contiguous blocks can be defined by a list of physical address / length pairs as follows: That is, the first entry 1000,50, the second entry 4000,80, the third and final entry 3500,
Defined as 20. In the "extent" file system, this file is first stored at physical address 1000
, Starting with 50, ie physical blocks 1000 to 1049. Subsequently, the file contains 800 data files starting from the physical address 4000.
It has blocks, i.e. 4000-4799. Finally, the file starts at physical address 3500 and starts at 20.
, Ie, blocks 3500 to 3519.

[0009]

This "extent"
There are a number of problems with typed file systems. For example, a file requires a large block of contiguous space,
If the available space is only a large number of small blocks at non-contiguous locations, the "extent" file system has a very long list of "physical address / length" pairs to specify one file. Will be. A second problem with the "extent" file system is that in order to retrieve the data block specified by the offset in the file, the software must search the entire "extent" list to find the data That is, the position of the block including the block must be found. Again, if the list is long, the search process to find the correct "physical address / length" pair can be a time consuming process. Finally, in the "extent" file system, the file storage is reconfigured to contiguous
If s) is improved, the "extent" list must be completely destroyed and a new "extent" list must be constructed. This requires a large amount of copy processing.

[0010] Therefore, improvements to reduce the indirect address search time and to reduce the size of the indirect address metadata are needed in the indirect address configuration.

[0011]

According to the present invention, when a logical address of a file is translated into a physical address in an indirect addressing file system, the pointer entry has a pointer and a pointer data indicator. Solved the above-mentioned problem. The conversion process uses computer implemented steps,
Start by retrieving an entry. Pointer
The pointer data indicator in the entry indicates a first state if the pointer points to a physical address in the data storage area and a second state if the pointer points to a lower level indirect address block. Show. After detecting whether the pointer data indicator is in the first state or the second state, the process takes two possible paths of operation. When the pointer data indicator is in the first state, the pointer is associated with the logical address and sets the physical address. When the pointer data indicator is in the second state, the logical address is divided into an index and an offset. The logical address is updated to the offset. Further, when the pointer data indicator is in the second state, the indirect address block pointed to by the current pointer and the designated indirect address block identified by the index.
From the given position in the address block), fetch the next pointer entry. The translation process repeats these steps until the physical address is set by combining the physical and logical addresses.

In another embodiment of the invention, the computer-implemented steps described above include a computer program of instructions that cause a computer to execute a computer process having the steps described above, ie, a computer-generated item. It is provided as a storage medium or a computer transmission medium.

In a machine embodiment of the present invention, the apparatus for translating logical address and pointer entries for files in an indirect address file system into physical addresses comprises a decision module, a set module, a split module, an update module. Module and a drawer module. The decision module examines a pointer flag in the current pointer entry. The pointer entry has a pointer and a pointer flag that identifies whether the pointer points to a data storage area or a metadata storage area. The decision module indicates whether the pointer is a data pointer or a metadata pointer. The set module is responsive to the decision module indicating that the pointer is a data pointer and combines the data pointer with the logical address to generate a physical address.

The partitioning module is responsive to the determining module indicating that the pointer is a metadata pointer,
A logical address as a first part as an index value;
It is divided into the remaining part as the offset value. The install module then sets the logical address to the offset value. The retrieval module combines the metadata pointer with the index value to get the next pointer entry. The fetch module sends the next pointer entry to the decision module to check whether the pointer is a data pointer or a metadata pointer, as indicated by the pointer flag in the next pointer entry. . All of the modules continue to process pointer entries as described above until the set module generates a physical address.

One of the features of the present invention is that the first pointer entry is a file control block, ie, an inode in a Unix file system.
Is given for the file by

As another feature of the present invention, each metadata
The pointer points to the next successive level of indirect addressing in the plurality of levels of indirect addressing. Each data pointer directly points to a data storage area. As a result, all levels of indirect addressing from the level having the pointer entry including the data pointer to the final indirect addressing level are bypassed.

A significant advantage and utility of the present invention is that, when a pointer flag or pointer data indicator is set, the indirect addressing process is:
Bypass all unnecessary levels of indirect addressing (circu
mvent), to go directly to the data storage area. In addition, if the pointer flag is not set, indirect addressing behaves just as if it had an indirect addressing file system.

The above and other features, utilities, and advantages of the present invention will become apparent from a more particular description of a preferred embodiment of the invention, as illustrated in the accompanying drawings.

[0019]

FIG. 1 shows the structure of the improved indirect addressing used in one embodiment of the present invention. The example of FIG. 1 has three levels of indirect addressing. As will be apparent in describing the present invention, the number of levels of indirect addressing is not critical to the present invention. The number of levels depends on the size of the file, the size of the indirect address block, the size of the data block, and the size of the pointer in the indirect address block. Shown in FIG. 1 contains a single file,
It is a three-level system.

In the structure of FIG. 1, the data blocks are stored in area 10 of the storage device. The storage device can be memory, but more typically is a disk file space. The data blocks in area 10 are addressed through indirect address blocks shown at levels 1, 2, 3 (L1, L2, L3). FIG.
Level 1 is a single root indirect address block 12, as shown in FIG. The size of the indirect address block 12 depends on the number of root addresses provided in the file system and is limited by the number of bits used in the root index portion of the offset used to address the file in the file system. Is done.

At level 2 (L2), three indirect address blocks 14, 16, 18 are shown. Potentially, for each pointer entry in the root address block 12 at level 1 (L1), there may be an address block at level 2. The size of the indirect address blocks 14, 16, 18 in L2 depends on the number of bits used in the level 2 index portion of the offset used to address the file in the file system. In the example of FIG. 1, the offset 20 is divided into four parts. The first three parts index addresses in the indirect address block at levels L1, L2, L3, respectively.
And each has 10 bits. The fourth part has 13 bits. Therefore, the maximum size of the indirect address block at level 2 or level 3 is 1,024 pointer entries. Also, L2
And L3 have only three indirect address blocks,
That is, in L2, blocks 14, 16, 18 and L
3 shows blocks 22, 24 and 26. Potentially, there are 1024 indirect address blocks in L2, one for each pointer entry in the root indirect address block 12. L3 also has 1024 indirect address blocks for each indirect address block in L2.

Each indirect address block has 1024
Pointer entry. As shown in the indirect address block 14, each pointer entry contains two types of information. That is, pointers and pointer data
Contains bits. The pointer data bit indicates whether the pointer points to a data block in data file area 10 or to the next lower level indirect address block.
If the pointer data bit is set, the pointer points to a data block in the data file area 10. If the pointer data bit is not set, the pointer points to the indirect address block at the next lower level of the address block. For example, in address block 14, pointer entry 28 includes pointer 28A and pointer data bit 28B. Pointer data bit 28B is one, so pointer 28A points to an entry point in data block storage area 10.

Pointer entry 30 in indirect address block 14 is an example of an entry that points to another indirect address block at the next lower level. Pointer entry 30 includes pointer 30A and pointer data bit 30B. Pointer data
Bit 30B is set to 0, so pointer 30A is at the next lower level, ie, level 3 (L
Point to the indirect address block 22 in 3).

The offset information at offset 20 is combined in various ways with these pointers to identify and retrieve data blocks within area 10. The index entry within offset 20 is used as an index and is combined with the pointer to identify the pointer entry at the next lower level of indirect addressing. Alternatively, a part of the offset 20 is used as the offset, and the data
It is also possible to identify the block position.

Indirect addressing starts with a pointer entry in an "inode" file in a Unix file. The pointer in the inode pointer entry points to the start address of the root indirect address block at level 1 (L1). Index 1 from offset 20 is combined with the starting address for the root indirect address block to find a pointer entry in the root indirect address block. A pointer entry in an inode may also include pointer data bits. When this pointer data bit is set, the pointer in the inode points directly to the start address in data storage area 10, and the entire offset indexes from this start address to the file data to be retrieved. . However, typically, the inode pointer entry has a pointer to the root indirect address block.

If the pointer data bit for the pointer entry in the root indirect address block 12 is 1, the pointer points directly to the starting point in the storage area 10. The pointer entry 32 has a pointer 32A pointing to the start address 34 at the top of the storage area 10. Pointer entry 32 is set to one, indicating that pointer 32 points to data storage area 10, pointer data bit 32.
B. The actual position of the data block drawn from area 10 is the pointer and Da at offset 20.
ta Offset Defined by the starting address identified by the 1 part. Therefore, for example, the pointer 32A
Indicates the physical address 11,000, and Data Offset 1
Is 350, the physical addresses in the area 10 from which data is extracted are 11,350. Thus, in response to the root address pointing to pointer entry 32 and the offset of 350, the data block at 11,350 is retrieved.

On the other hand, the route at level 1 (L1)
If the pointer entry in the address block has a pointer data bit set to 0, the pointer points to an indirect address block in L2. For example, if the pointer in the root address block points to the indirect address block 14 in L2, the pointer entry in the address block 14 is retrieved based on Index 2 in offset 20. In other words, the high order bit in offset 20 functions as an index and is combined with the pointer from the pointer entry in root address block 12 to find the pointer entry in the indirect address block at level two.

If the pointer entry retrieved at L2 has a pointer data bit set to 1, for example, pointer entry 28 in indirect address block 14, the remaining Data at offset 20 Offset 2 is used as a data offset, or index, and is combined with the pointer in pointer entry 28 to find a data block in storage area 10. For example, when the pointer 28A is in the area 1
0 indicates a physical address of 2,000, and offset 2
If Data Offset 2 in 0 is 400, the data block at physical address 2400 is stored in storage area 10
Drawn from.

On the other hand, if the pointer data bit in the pointer entry at level 2 (L2) is 0, the pointer simply points to the indirect address block at level 3 (L3). The indirect address blocks in L3 all have pointer data bits set to one. The reason is that level 3 is the lowest level of indirect addressing, and the pointer at level 3 must point to a physical address in the data storage area 10. Thus, when using level 3 of indirect addressing, the Index 3 portion of offset 20 is combined with the pointer from L2 to find the pointer entry in the indirect address block at L3.
The Data Offset 3 portion of offset 20 is also combined with the pointer from the pointer entry in L3,
The physical address in the storage area 10 is found.

When using all three levels, this structure has no advantage over conventional indirect addressing. However, if contiguous data blocks are present, this structure provides a structure for addressing a larger data block in contiguous space directly from a higher indirect address level. First, the pointer data bits indicate that the pointer in the higher level pointer entry points directly to a physical address in storage area 10. Second, depending on the level of the pointer entry, a higher level pointer to this physical address is combined with all or part of the offset to retrieve data from a physical address in storage area 10. In this way, unnecessary low-level indirect addressing can be bypassed.

The operating environment in which the present invention is used includes not only a general-purpose distributed computer system but also a single computer system. In a distributed computer system, a general purpose computer, workstation, or personal computer is coupled to a client-server configuration through various types of communication links, often storing programs and data in the form of objects, within the system. It can be used by component devices.

Some of the elements of a stand alone computer or a general purpose workstation computer are shown in FIG. In accordance with the present invention, a user located at a remote workstation in the network, such as a client processor 35, allows a computer
It communicates with the server 20. The server 20 includes an input / output unit 22,
It includes a central processing unit 23 and a processor 21 having a memory unit 24. The input / output unit 22 is optionally connected to a keyboard 25, a display or monitor 26, and a disk storage device 29. Input / output unit 22 includes a communication adapter (not shown) for communicating with remote client station 35 on network 46.

An application program 45 runs on the client station 35 and can access or change files maintained by the server 20. The computer program product for performing the apparatus and method of the present invention can be located in the memory unit 24 or on a disk storage device 29 or similar storage medium (not shown), or the storage medium used by the client 35. It is also possible to put on top. Examples of computer systems that can be used as either server 20 or client 35 include PARC provided by Sun Microsystems.
Includes personal computers and systems that run operating systems such as UNIX, OS / 2, HP-UX, AIX, DOS, etc. provided by J Systems, IBM, and the manufacturers of IBM compatible personal computers.
SPARC is a trademark of Sun Microsystems, and UNIX is X
OS / 2 and AIX are trademarks of IBM Corporation, licensed under the trademark / Open.

As shown in FIG. 2, client 35 and server 20 communicate over network 46 to provide client 35 with access to files maintained on disk 29 of the server. Conversely, the client 35 also needs to
The file data is transferred through the network 46.

FIG. 3 illustrates the logical processing in the preferred embodiment of the present invention for translating a logical address into a physical address in the improved indirect addressing structure of the present invention and extracting a data block at the physical address. In FIG. 3, when the process 100 extracts the offset and sets the logical address to the offset as the initial address for the file, the conversion process starts. Next, operation 102 retrieves a pointer entry from the file control block (inode) for the file.

The judgment processing 106 determines that the drawer module 1
A check is made as to whether the pointer data bit of the pointer entry just retrieved by 02 is set. If the pointer data bit is set, the translation process knows that the pointer points to a data storage area. The processing flow branches from the determination processing 106 to “Yes”, and proceeds to the withdrawal processing 108. Retrieve operation 108 retrieves the pointer from the pointer entry, then operation 110 sets the physical address for the file to the pointer plus the logical address. In this case, the logical address is the entire offset 20 (FIG. 1). The physical address set in the process 110 is then used by the retrieval process 112 to retrieve the data block at the physical address. The conversion process is completed by extracting the data block.

If the decision process 106 detects that the pointer data bit is not set, ie, that the pointer in the pointer entry points to an indirect address block, the process flow proceeds to decision process 106.
To “No”. Next, the processing flow moves to the withdrawal module 104. In the example of FIG. 1, the retrieval module 104 of FIG. 3 retrieves the root indirect address block indicated here by the pointer in the pointer entry from the inode. Next, the division module 114 determines that the offset 2
The logical address set to 0 (FIG. 1) is divided into an index part and an offset part. In this case, the logical address is divided into Index 1 and Data Offset 1 (FIG. 1). Operation 116 sets the new logical address to the offset that was split from the previous logical address in operation 114. As a result, the logical address is
Will be set to Data Offset 1.

Operation 118 may proceed before or in parallel with operation 116, using the index split from the previous logical address by operation 114 to find a new pointer entry. Operation 118 retrieves a new pointer entry from the indirect address block retrieved by module 104 at the location identified by the index. In the case of FIG. 1, the pointer points to the root indirect address block 12 and Index 1 identifies the pointer entry 32.
After the new pointer entry 32 has been retrieved by operation 118, processing flow returns to decision operation 106.

As long as decision operation 106 detects that the pointer data bit in the pointer entry is not set (ie, the pointer data bit is equal to zero), the process flow remains in loop 120. .
For each pass through this loop, process 104 retrieves the indirect address block pointed to by the pointer in the pointer entry just retrieved by process 118 during the immediately preceding pass. Division module 1
14 divides the logical address updated in the previous pass into an index and an offset value. FIG.
In the example, the second pass through the loop 120 divides the offset 20 into Index 2 and Data Offset 2. Further, the logical address in the second pass is updated to Data Offset 2 by the processing 116, and the next pointer entry is extracted by the processing 118. The next pointer entry is at the position of Index 2 in the indirect address block at level 2 (L2) derived by operation 104. For example, if pointer entry 33 was drawn from the root indirect address block during the first pass, process 104 pulls indirect address block 16 during the second pass and process 1
18 will retrieve pointer entry 35 based on Index 2 during the second pass.

After the second loop 120 pass (eg, pointer entry 35), if the pointer data bit in the next pointer entry has not yet been set, the third loop 120 pass will Operation 114 sets the new offset to Index 3 and Data Offs
Divide into et 3. In the third pass, level 3 (L
The indirect address block in 3) is extracted, and the pointer entry in the indirect address is extracted by processing 118. This pointer entry at the lowest level L3 is the pointer data data set to one.
Always have a bit. Therefore, at the end of the third pass, the determination process 106 always branches to “Yes”. Thus, the processes 108 and 110 set the physical address to the value obtained by adding the logical address, here Data Offset 3, to the pointer from the pointer entry at level 3.

As in the above example, the pointer data with all of the pointer entries set to "0"
With bits, there is no advantage over conventional indirect addressing. The utility and great advantage of the present invention is that if the pointer data bit in the pointer entry is set to "1" at any time from the inode through any level higher than the lowest level 1 in that the pointer and the remaining offset can directly address a data block in the storage area 10 of FIG. An example where the pointer entry in the inode points to the data storage area 10 has already been discussed with reference to FIG.

FIG. 4 shows that the pointer data bit in the inode pointer entry is set to "0" (not indicating data) and the pointer entry 1 in the level 1 or root indirect address block 12 is shown.
This is an example where the pointer data bit 130A in 30 is set to 1 (indicating data). Pointer entry 130 is located by combining Index 1 with a pointer from the inode. Pointer 130 in pointer entry
B indicates a start address 132 in the data storage area 10. The data in the file has a start address 132
Is found at the physical address equal to Data Offset 1. In this example, the indirect addressing levels L2 and L3 are bypassed.

FIG. 5 shows an example in which the pointer data bit is not set up to the pointer entry 134 at level 2. Here, the loop 120 of FIG.
Need to be passed twice. 2 passing through loop 120
During the second pass, Index 2 is the pointer entry 136 in the level 1 root indirect address block 12.
Used to find the pointer entry 134 at level 2 with the pointer 136B from. Data Offse
t 2 is the indirect address block 13 at level 2
8 pointer entry 134, pointer 13
4B, which directly indicates the data start address in the data storage area 10. The data location in the file is found at the physical address, which is equal to the start address 140 plus Data Offset 2. In this example, the level L3 of indirect addressing is bypassed.

In both FIGS. 4 and 5, saving of data storage area for metadata, and
Saved time when reaching the block area. If the pointer data bits are not available, use all three indirect levels of addressing,
The preferred embodiment operates as efficiently as there is no pointer data bit in variable offset addressing. Therefore, the improved indirect addressing of the present invention enables optimization of indirect addressing, and does not adversely affect indirect addressing even when optimization is not possible.

While the present invention has been particularly shown and described with reference to preferred embodiments thereof, various other forms and details are possible without departing from the spirit and scope of the invention. Those skilled in the art will appreciate that modifications are possible.

[Brief description of the drawings]

FIG. 1 is an address data flow diagram illustrating the structure of improved indirect addressing according to a preferred embodiment of the present invention.

FIG. 2 illustrates a distributed processing computer system in which a server and a number of clients are connected in a communication network and the servers and clients can perform the logical processing of the present invention when addressing data.

FIG. 3 is a diagram showing an operation flow of a logical process for converting a file offset address into a physical address according to the preferred embodiment of the present invention.

FIG. 4 is a diagram showing the flow of address data when the improved indirect address indicates a data block from the highest level of the indirect address block.

FIG. 5 is a diagram showing the flow of address data when an improved indirect address indicates a data block from an intermediate level indirect address block.

[Explanation of symbols]

10 Storage Area 12 Indirect Address Block 14, 16, 18, 22, 24, 26 Indirect Address Block 20 Offset 28, 30, 32 Pointer Entry 28A, 30A, 32A Pointer 28B, 30B, 32B Pointer Data Bit 34 Start address

 ──────────────────────────────────────────────────続 き Continuation of front page (71) Applicant 597004720 2550 Garcia Avenue, MS PAL1-521, Mountain View, California 94043-1100, United States of America

Claims (21)

[Claims] 1. A method for translating a logical address of a file into a physical address in a file system, comprising:
The file system has an indirect address block with a pointer entry, the method comprising: (a) retrieving a first pointer entry, the pointer entry comprising a pointer and a pointer data data. An indicator and the pointer data
The indicator indicates a first state when the pointer points to a physical address in the data storage area;
Indicating a second state if the pointer points to a lower level indirect address block; and (b) determining whether the pointer data indicator is in the first state or the second state. Detecting; (c) combining the pointer and the logical address to set a physical address when the pointer data indicator is in the first state; and (d) the pointer data indicator. In the second state, dividing the logical address into an index and an offset, and updating the logical address to the offset; and (e) when the pointer data indicator is in the second state. Is in the specified indirect address block pointed to by the current pointer, and One step (d)
Retrieving the next pointer entry at the location in the designated indirect address block identified by the index from (f); and (f) until the physical address is set by step (c). Or repeating step (e). 2. The method of claim 1, wherein the first
The method wherein the pointer entry is from a file control block. 3. The method according to claim 1, wherein said pointer data indicator is a pointer data bit. 4. The method of claim 1, further comprising: (g) retrieving a block of data at the physical address set by step (c). 5. The method of claim 1, wherein step (e) comprises: (h) locating a start address of the specified indirect address block specified by a current pointer; and (i) determining the index by the index. Retrieving the next pointer entry at the location in the designated indirect address block identified by the index, combined with the starting address from the current pointer. 6. The method of claim 5, wherein step (c) comprises: (j) locating a data start address of a data storage area designated by a current pointer; and (k) retrieving said logical address to said current address. Adding to a data start address from a pointer and setting a physical address for a data block in the data storage area. 7. An apparatus for translating a logical address and a pointer entry for a file in an indirect address file system into a physical address, said file system having a plurality of levels of indirect addressing in a metadata storage area. A determination module for checking a pointer flag in a current pointer entry, wherein the pointer entry identifies a pointer and whether the pointer points to a data storage area or the meta storage area. Responding to the determination module to indicate that the pointer is a data pointer or a metadata pointer, and to the determination module to indicate that the pointer is a data pointer, Data pointer to the logical address Set to generate the bound physical address and -
A dividing module responsive to the determining module indicating that the pointer is a metadata pointer, dividing the logical address into a first part as an index value and a remaining part as an offset value; An update module that sets the logical address to the offset value from the split module; combining the metadata pointer with the index value to obtain a next pointer entry;
A withdrawal module for sending an entry to the determination module, wherein a check is made as to whether the pointer is a data pointer or a metadata pointer by a pointer flag in the next pointer entry. , Until all of the set modules generate a physical address,
An apparatus for processing an entry. 8. The apparatus according to claim 7, wherein the first
An apparatus wherein the pointer entry is provided by a file control block. 9. The apparatus of claim 7, further comprising a data block access module responsive to a physical address from said set module and accessing a data block at said physical address. Characteristic device. 10. The apparatus of claim 7, wherein each metadata pointer points to a next successive level of indirect addressing in the plurality of levels of indirect addressing, and each data pointer points to the data storage area. Indicating, bypassing all levels of indirect addressing from the level having the pointer entry including the data pointer to the last indirect addressing level;
An apparatus characterized in that: 11. The apparatus according to claim 7, wherein the metadata pointer indicates a block start address for the indirect address block, and the extraction module adds the index value to the block start address. And determining the position of the next pointer entry. 12. The apparatus of claim 11, wherein the data pointer points to a data start address in the data storage area, the set module adds the logical address to the data start address, An apparatus for generating a physical address. 13. A computer program storage medium readable by a computer system and encoding a computer program of instructions for executing a computer process for translating a logical address of a file to a physical address in a file system. Wherein the file system has an indirect address block with a pointer entry, the computer process comprising: (a) retrieving a first pointer entry, wherein the pointer entry is a pointer entry; And a pointer data indicator.
The indicator indicates a first state when the pointer points to a physical address in the data storage area;
Indicating a second state if the pointer points to a lower level indirect address block; and (b) determining whether the pointer data indicator is in the first state or the second state. Detecting; (c) combining the pointer and the logical address to set a physical address when the pointer data indicator is in the first state; and (d) the pointer data indicator. In the second state, dividing the logical address into an index and an offset, and updating the logical address to the offset; and (e) when the pointer data indicator is in the second state. Is in the specified indirect address block pointed to by the current pointer, and One step (d)
Retrieving the next pointer entry at the location in the designated indirect address block identified by the index from (f); and (f) until the physical address is set by step (c). Or a step of repeating step (e). 14. The computer program storage medium according to claim 13, wherein in the computer program, the first pointer entry is from a file control block. . 15. The computer program storage medium according to claim 13, wherein in the computer program, step (e) comprises: (g) a start address of the specified indirect address block specified by a current pointer. And (h) combining the index with the starting address from the current pointer to retrieve the next pointer entry at the location in the designated indirect address block identified by the index. A computer program storage medium, comprising: 16. The computer program storage medium according to claim 13, wherein in the computer program, step (c) comprises: (i) locating a data start address of the data storage area specified by the current pointer. And (j) adding the logical address to a data start address from the current pointer, and setting a physical address for a data block in the data storage area. Storage medium. 17. A computer program transmission medium for storing a computer program downloaded from a first computer system to a second computer system during transmission, the computer program transmission medium comprising an indirect address file Encoding a computer program of instructions for executing a computer process that translates logical and pointer entries for files in a system into physical addresses, said file system comprising a plurality of levels of indirect addressing in a metadata storage area; Examining a pointer flag in a current pointer entry, the pointer entry comprising a pointer and a pointer to the data storage area or metadata record. A pointer flag for identifying which of the areas is to be indicated, the checking step indicating that the pointer is a data pointer or a metadata pointer, and that the pointer is a data pointer. A first combining step of combining the data pointer with the logical address to generate a physical address in response to the checking step, and responding to the checking step indicating that the pointer is a metadata pointer. Dividing the logical address into a first part as an index value and a remaining part as an offset value; updating the logical address to the offset value; A second combining step for combining with the index value to obtain the next pointer entry Returning the next pointer entry to the checking step and checking whether the pointer flag in the next pointer entry indicates whether the pointer is a data pointer or a metadata pointer. Performing all of the steps until the first combining step generates a physical address, wherein all of the steps continue to process pointer entries. 18. The computer program transmission medium according to claim 17, wherein said computer process in said computer program further comprises a step of accessing a data block at said physical address. Program transmission medium. 19. The computer program of claim 17, wherein each metadata pointer points to the next successive level of indirect addressing in the plurality of levels of indirect addressing. A computer characterized in that the pointer bypasses all levels of indirect addressing from the level having the pointer entry including the data pointer to the last indirect addressing level by pointing to the data storage area. Program transmission medium. 20. The computer program according to claim 19, wherein the metadata pointer indicates a block start address for an indirect address block, and the second combining step includes: Adding the index value to the block start address to determine the position of the next pointer entry. 21. The computer program according to claim 20, wherein the data pointer points to a data start address in the data storage area, and wherein the first combining step includes the logical address. To the data start address to generate the physical address.