Link storage structure of simulated design disk file

Subject requirements

1. The management of disk files adopts explicit link structure , Record the physical block number and link pointer occupied by the file In a file allocation table （FAT） in . The block number of the first block of the file is recorded in the index node . File directory Only the file name and index node number are recorded . The structure of the index node is as follows ：

1. Assume that the disk storage space has a total of 100 Physical blocks are used to store data , Catalog files and index nodes can be Direct access , Not here 100 In blocks .
2. A physical block can store 3 File logic records , And assume that the logical record of the file is fixed .
3. It is required to simulate the user's read / write request by keyboard input , The menu format is suggested as follows ：
   • Create（filename）
   • Write（filename, text, logical_record_no）
   • Read (filename, logical_record_no)
   • Delete（filename） among filename Is the file name to read and write ,text Is what is written ,logical_record_no It's logic Record No .Create、Write、Read、Delete Each represents creating a file , To a certain logic of the file Compilation record writing , Read from a logical record of a file , Delete a file .
4. File storage space management adopts bit diagram （ The position diagram is 7 That's ok ,16 Column ） The way .
5. Request that the program can print FAT And the position diagram .

The structure design

data structure

Node item

typedef struct Inode {
    int firstBlockId;     //  The first block number of the file 
    int lastBlockId;      //  The last block number of the file 
    int usedBlocksNum;    //  Number of disk blocks occupied by the file 
    time_t createTime;    //  File creation time 
    time_t LastEditTime;  //  The last time the file was modified 
    int permission;       //  File permissions 
    int isDelete;         //  Whether the node is marked “ deleted ”
    char standby[20];     //  spare 
} Inode;

Copy

Catalog items

typedef struct listItem {
    char fileName[256];  //  File name 
    int nodeId;          //  Node number corresponding to the file 
} listItem;

Copy

Physical disk block number

typedef struct Block {
    //  Each physical block has three logical record numbers 
    char firstLogical[LOGICALSIZE];
    char secondLogical[LOGICALSIZE];
    char thirdogical[LOGICALSIZE];
} Block;

Copy

Abstract disk

typedef struct Disk {
    int FAT[BLOCKNUM];             //  At most BLOCKNUM Table items 
    int bitmap[ROW][COL];          //  Display bitmap 
    listItem directory[BLOCKNUM];  //  Catalog   At most BLOCKNUM Catalog items 
    Inode FDI[BLOCKNUM];  //  Index node set   At most BLOCKNUM Nodes 
    int fileNum;
    Block blocks[BLOCKNUM];  //  Total number of physical disks 
    int freeBlock;           //  Number of free disk blocks 
} Disk;

Copy

Design thinking

The program starts by formatting the disk , Then perform relevant operations according to the user's choice .

• create a file ： First, apply for a free disk （ That is, a file initially occupies one disk by default ）, At the same time, record the applied disk as “ Already used ” state . The application method is ： Choose a random number as “ Base address ”, If the disk block has been occupied , Try to apply for this “ Base address ” Next piece of , If it is still occupied , Then continue to try later ………
• Read the file ： According to the file name , Retrieve... In the directory , Find the index node corresponding to the file . Then try to read according to the logical record number to be read （ The maximum logical record number of a file is ：max = 3 * n - 1,n Is the number of disk blocks occupied by the file , That is, the number starts from zero ）. The method is ： The first disk block number occupied by the file is obtained according to the index node obtained from the search directory , If the disk block is not the disk block that the user wants to read , Get the next disk block number according to the file allocation table , Repeat the above process , Until the destination block number is found .
• write file
  • Write data ： Write data to a logical record number of a file , Check the validity of the logical record number before writing
  • Modify the file size ： If the new file size is smaller than the old file size , Only the data of the new file size
• Delete file ： First, according to the file name , Retrieve the corresponding index node in the directory , Get the first disk block number according to the index node , Set the disc block to “ Unused state ”, And point this disk to the next disk （ If there is ） Also set to “ not used ”, Repeat accordingly , Until all the disk blocks occupied by the file are returned . At the same time, the display map corresponding to the disk block should also be updated .

Source program

/*
 * @Author: YaleXin
 * @Date: 2020-06-07 15:53:40
 * @LastEditTime: 2020-07-01 21:08:41
 * @LastEditors: YaleXin
 * @Description:  Operating system course design 
 * @FilePath: \my_c_workspace\OS\design\main.c
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LOGICALSIZE 1024  // The size of a logical record 
#define BLOCKNUM 100      // Number of physical blocks 
#define ROW 7             // Shows the number of lines in the bitmap 
#define COL 16            // Show the number of bitmap Columns 
#define FREE 0            // The idle state is indicated in the bitmap 
#define USED 1            // The used status is indicated in the bitmap 
const int OK = 1;
/**
 *  Catalog items 
 */
typedef struct listItem {
    char fileName[256];  //  File name 
    int nodeId;          //  Node number corresponding to the file 
} listItem;
typedef struct Block {
    //  Each physical block has three logical record numbers 
    char firstLogical[LOGICALSIZE];
    char secondLogical[LOGICALSIZE];
    char thirdogical[LOGICALSIZE];
} Block;
typedef struct Inode {
    int firstBlockId;     //  The first block number of the file 
    int lastBlockId;      //  The last block number of the file 
    int usedBlocksNum;    //  Number of disk blocks occupied by the file 
    time_t createTime;    //  File creation time 
    time_t LastEditTime;  //  The last time the file was modified 
    int permission;       //  File permissions 
    int isDelete;         //  Whether the node is marked “ deleted ”
    char standby[20];     //  spare 
} Inode;
typedef struct Disk {
    int FAT[BLOCKNUM];             //  At most BLOCKNUM Table items 
    int bitmap[ROW][COL];          //  Display bitmap 
    listItem directory[BLOCKNUM];  //  Catalog   At most BLOCKNUM Catalog items 
    Inode FDI[BLOCKNUM];  //  Index node set   At most BLOCKNUM Nodes 
    int fileNum;
    Block blocks[BLOCKNUM];  //  Total number of physical disks 
    int freeBlock;           //  Number of free disk blocks 
} Disk;
Disk d;
int dirLastIndex;  //  The last table of contents entry subscript 
int fdiLastIndex;  //  The last index node subscript 
/**
 *  Successful application , The requested physical block number is returned 
 *  Otherwise return to -1
 */
int getFreeBlock() {
    if (d.freeBlock <= 0) return -1;
    //  Apply for a physical block randomly   If it has been used    Then look back 
    srand((unsigned)time(NULL));
    int index = rand() % BLOCKNUM;
    int r = index / 16, c = index % 16;
    if (d.bitmap[r][c] == 0) {
        d.bitmap[r][c] = 1;
        d.freeBlock--;
        return index;
    } else {
        int i, j;
        if (c == 15) {
            i = (r + 1) % 7;
            j = 0;
        } else {
            i = r;
            j = (c + 1) % 16;
        }
        for (; i < 7; )
            for (; j < 16; ) {
                if (d.bitmap[i][j] == 0) {
                    d.bitmap[i][j] = 1;
                    d.freeBlock--;
                    return (i * 16 + j);
                }
                j++;
                if(j == 16){
                    i = (i + 1)%7;
                    j = 0;
                }
            }
    }
}
/**
 *  format 
 */
void intial() {
    for (int i = 0; i <= 99; i++) d.FAT[i] = EOF;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++) d.bitmap[i][j] = FREE;
    for (int i = 0; i < BLOCKNUM; i++) {
        d.blocks[i].firstLogical[0] = '\0';
        d.blocks[i].secondLogical[0] = '\0';
        d.blocks[i].thirdogical[0] = '\0';
    }
    d.fileNum = 0;
    dirLastIndex = 0;
    fdiLastIndex = 0;
    d.freeBlock = BLOCKNUM;
}
/**
 *  Error code ：
 * 2： file already exist 
 * 3： Insufficient disk space 
 */
int Create(char *fileName) {
    for (int i = 0; i < dirLastIndex; i++)
        if (!strcmp(d.directory[i].fileName, fileName) &&
            d.directory[i].nodeId != -1) {
            return 2;
        }
    int blockId = getFreeBlock();
    if (blockId == -1) {
        return 3;
    } else {
        int i;
        for (i = 0; i < fdiLastIndex; i++)
            if (d.FDI[i].isDelete) break;
        //  Handle index nodes 
        d.FDI[i].firstBlockId = d.FDI[i].lastBlockId = blockId;
        //  Get the current timestamp 
        time(&(d.FDI[i].createTime));
        d.FDI[i].LastEditTime = d.FDI[i].createTime;
        d.FDI[i].permission = 444;
        d.FDI[i].usedBlocksNum = 1;
        d.FDI[i].isDelete = 0;
        int j;
        for (j = 0; j < dirLastIndex; j++)
            if (d.directory[j].nodeId == -1) break;
        //  Processing catalog entries 
        strcpy(d.directory[j].fileName, fileName);
        d.directory[j].nodeId = i;
        if (i == dirLastIndex) dirLastIndex++;
        if (j == fdiLastIndex) fdiLastIndex++;
        d.fileNum++;
        return OK;
    }
}
struct readReturn {
    int status;
    char msg[LOGICALSIZE];
};
/**
 *  Return value ：
 * 1: Read normal 
 * 2: file does not exist 
 * 3: Logical record number error 
 */
struct readReturn Read(char *filename, int logical_record_no) {
    struct readReturn r;
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(filename, d.directory[i].fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) {
        r.status = 2;
        return r;
    }
    int BlockId = logical_record_no / 3;
    if (BlockId + 1 > d.FDI[d.directory[i].nodeId].usedBlocksNum) {
        r.status = 3;
        return r;
    }
    int index = d.FDI[i].firstBlockId;
    for (int j = 0; j < BlockId; j++) index = d.FAT[index];
    switch (logical_record_no % 3) {
        case 0:
            strcpy(r.msg, d.blocks[index].firstLogical);
            break;
        case 1:
            strcpy(r.msg, d.blocks[index].secondLogical);
            break;
        case 2:
            strcpy(r.msg, d.blocks[index].thirdogical);
            break;
    }
    r.status = 1;
    return r;
}
/**
 *  Error code ：
 * 2： file does not exist 
 * 3： Logical record number error 
 */
int Write(char *filename, char *text, int logical_record_no) {
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(filename, d.directory[i].fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) return 2;
    if (logical_record_no < 0 ||
        logical_record_no >= d.FDI[i].usedBlocksNum * 3)
        return 3;
    //  adopt  firstBlockId  stay  FAT  To find the correct location to write 
    int index = d.FDI[i].firstBlockId, blockId = logical_record_no / 3;
    for (int j = 0; j < blockId; j++) index = d.FAT[index];
    switch (logical_record_no % 3) {
        case 0:
            strcpy(d.blocks[index].firstLogical, text);
            break;
        case 1:
            strcpy(d.blocks[index].secondLogical, text);
            break;
        case 2:
            strcpy(d.blocks[index].thirdogical, text);
            break;
    }
    //  Get the current timestamp 
    time(&(d.FDI[i].LastEditTime));
    return OK;
}
void tryCreate() {
    char fileName[256];
    printf(" Please enter a new file name ：\n");
    scanf("%s", fileName);
    int status = Create(fileName);
    if (status == 2)
        printf(" The file already exists , Please delete the old file before creating it .\n");
    else if (status == 3)
        printf(" Insufficient disk space ！ Unable to create new file .\n");
    else
        printf(" Create success !\n");
    system("pause");
}
void tryRead() {
    char fileName[256];
    int logical_record_no;
    printf(" Please enter the file name you want to read ：\n");
    scanf("%s", fileName);
    printf(" Please enter the logical record number you want to read （ The number starts from zero ）：\n");
    scanf("%d", &logical_record_no);
    struct readReturn r = Read(fileName, logical_record_no);
    if (r.status == 2) {
        printf(" The file does not exist ！ Please re-enter the file name .\n");
    } else if (r.status == 3) {
        printf(" The file does not have the logical record , Please enter the correct logical record number .\n");
    } else {
        printf(" What I read is \n%s\n", r.msg);
    }
    system("pause");
}
void tryWrite() {
    char fileName[256], text[1024];
    int logical_record_no, newBlockSize;
    int exit = 0, choice;
    while (!exit) {
        system("cls");
        printf("1. Write data to file \n");
        printf("2. Modify the file size \n");
        printf("0. return \n");
        printf(" Please enter your choice ：\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1: {
                printf(" Please enter the file name you want to write ：\n");
                scanf("%s", fileName);
                printf(" Please enter the logical record number you want to write （ The number starts from zero ）：\n");
                scanf("%d", &logical_record_no);
                printf(" Please enter the information you want to write （ Write at most %d Characters ）\n",
                       LOGICALSIZE);
                getchar();
                gets(text);
                int status = Write(fileName, text, logical_record_no);
                if (status == 2) {
                    printf(" file does not exist , Please enter the correct file name ！\n");
                } else if (status == 3) {
                    printf(
                        " The logical record number you entered is too large or negative , You can increase the file size "
                        " Small makes the file have the logical record number \n");
                } else {
                    printf(" Write successfully ！\n");
                }
                system("pause");
                break;
            }
            case 2: {
                printf(" Please enter the file name you want to modify ：\n");
                scanf("%s", fileName);
                printf(
                    " Please enter the new size of the file （ If new size is smaller than original size , Only the new "
                    " Size data , The new size should be a number greater than zero , Company ： block ）：\n");
                scanf("%d", &newBlockSize);
                //  Index node subscript 
                int i;
                for (i = 0; i < dirLastIndex; i++)
                    if (!strcmp(fileName, d.directory[i].fileName) &&
                        d.directory[i].nodeId != -1)
                        break;
                if (i >= dirLastIndex) {
                    printf(" file does not exist , Please enter the correct file name ！\n");
                    system("pause");
                    break;
                } else if (newBlockSize > d.FDI[i].usedBlocksNum) {
                    //  Increase the file size 
                    int need = newBlockSize - d.FDI[i].usedBlocksNum, blockId;
                    while (need) {
                        blockId = getFreeBlock();
                        if (blockId == -1) {
                            printf(
                                " Insufficient disk space ！ Only successfully applied  %d "
                                " A physical block , Application failed  %d  individual \n",
                                newBlockSize - need, need);
                            system("pause");
                            break;
                        }
                        need--;
                        d.FAT[d.FDI[i].lastBlockId] = blockId;
                        d.FDI[i].lastBlockId = blockId;
                        d.FDI[i].usedBlocksNum++;
                    }
                    time(&(d.FDI[i].LastEditTime));
                    printf(" Modification successful ！\n");
                    system("pause");
                    break;
                } else if (newBlockSize < d.FDI[i].usedBlocksNum) {
                    //  Reduce file size 
                    int index = d.FAT[d.FDI[i].firstBlockId], count = 1;
                    while (count < newBlockSize) {
                        index = d.FAT[index];
                        count++;
                    }
                    //  Reclaim the following disk space 
                    while (newBlockSize - count > 0) {
                        int old = d.FAT[index];
                        index = d.FAT[index];
                        d.FAT[old] = EOF;
                        count++;
                    }
                    time(&(d.FDI[i].LastEditTime));
                    printf(" Modification successful ！\n");
                    system("pause");
                    break;
                }
            }
            case 0:
                return;
            default:
                printf(" Your input is wrong , Please re-enter ！\n");
                system("pause");
                break;
        }
    }
}
void showBitmap() {
    printf("“0” For leisure ,“1” Represents used \n");
    for (int i = 0; i < 7; i++)
        for (int j = 0; j < 16; j++) {
            if (i * 16 + j >= BLOCKNUM) {
                printf("\n");
                system("pause");
                return;
            } else {
                printf("%d ", d.bitmap[i][j]);
            }
            if (j == 15) printf("\n");
        }
}
void showFiles() {
    printf(
        "----------------------------------------------------------------------"
        "--------------\n");
    printf("|%-20s|%-19s|%-19s|%-10s|%-10s|\n", " file name ", " Date of creation ",
           " modification date ", " Permission information ", " file size ");
    for (int i = 0; i < dirLastIndex; i++)
        if (d.directory[i].nodeId != -1) {
            printf(
                "|%-20s|%4d-%2d-%2d %2d:%2d:%2d|%4d-%2d-%2d "
                "%2d:%2d:%2d|%-10d|%-10d|\n",
                d.directory[i].fileName,
                //  Year from 1900 From the beginning , So add 1900
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_year +
                    1900,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_mon + 1,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_mday,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_hour + 8,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_min,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_sec,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_year +
                    1900,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_mon +
                    1,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_mday,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_hour +
                    8,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_min,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_sec,
                d.FDI[d.directory[i].nodeId].permission,
                d.FDI[d.directory[i].nodeId].usedBlocksNum);
        }
    printf(
        "----------------------------------------------------------------------"
        "--------------\n");
    system("pause");
}
/**
 *  Error code ：
 * 2： file does not exist 
 */
int Delete(char *fileName) {
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(d.directory[i].fileName, fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) return 2;
    int nextIndex = d.FDI[d.directory[i].nodeId].firstBlockId;
    int row, col, pre;
    while (d.FAT[nextIndex] != EOF) {
        row = nextIndex / COL;
        col = nextIndex % COL;
        d.bitmap[row][col] = FREE;
        pre = nextIndex;
        nextIndex = d.FAT[nextIndex];
        d.FAT[pre] = -1;
    }
    row = nextIndex / COL;
    col = nextIndex % COL;
    d.bitmap[row][col] = FREE;
    d.FDI[d.directory[i].nodeId].isDelete = 1;
    d.directory[i].nodeId = -1;
    return OK;
}
void tryDelete() {
    char fileName[11];
    printf(" Please enter the file you want to delete ：\n");
    scanf("%s", fileName);
    int status = Delete(fileName);
    if (status == 2) {
        printf(" The file does not exist , Please re-enter !\n");
    } else {
        printf(" Delete successful ！\n");
    }
    system("pause");
}
void showFAT() {
    int i = 0, len = 25, j = 1, t, k;
    for (; j <= 4; j++) {
        t = i;
        for (k = 1; k <= 114; k++) printf("-");
        printf("\n");
        printf("|%-12s|", " Number ");
        for (; i < j * len; i++) printf("%-3d|", i);
        printf("\n");
        printf("|%-12s|", " The number of the next disk ");
        for (i = t; i < j * len; i++) printf("%-3d|", d.FAT[i]);
        printf("\n");
        for (k = 1; k <= 114; k++) printf("-");
        printf("\n\n");
    }
    system("pause");
}
int main() {
    //  Initialize disk   Format 
    intial();
    int exit = 0, choice;
    while (!exit) {
        system("cls");
        printf("1. create a file \n");
        printf("2. Read the file \n");
        printf("3. write file \n");
        printf("4. Delete file \n");
        printf("5. Display bitmap \n");
        printf("6. List all files \n");
        printf("7. Print FAT\n");
        printf("0. Exit the system \n");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                tryCreate();
                break;
            case 2:
                tryRead();
                break;
            case 3:
                tryWrite();
                break;
            case 4:
                tryDelete();
                break;
            case 5:
                showBitmap();
                break;
            case 6:
                showFiles();
                break;
            case 7:
                showFAT();
                break;
            case 0:
                exit = 1;
                break;
            default:
                printf(" Incorrect input , Please re-enter ！\n");
                system("pause");
                break;
        }
    }
}

Copy

episode

Ten minutes before the acceptance, I suddenly found getFreeBlock() Function has bug, At that time, he immediately withdrew from the Tencent meeting , After testing for a long time, I found that for There's something wrong with the loop , It was written like this before ：

for (; i < 7; i =( i + 1 ) % 7)
    for (; j < 16; j = (j + 1) % 16) {
                
}

Copy

In this way, the inner loop can never end , It creates an endless cycle . I haven't found this problem before because during the previous test , Generally, the file size will not be changed greatly , So this loop will not be triggered .