[xv6] inode

글의 참고

- https://github.com/mit-pdos/xv6-public/tree/master

- xv6 - DRAFT as of September 4, 2018

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

: 아래는 `xv6`의 `fs.c` 파일에서 `inode`에 대해 설명하는 글이다. 중요한 변수 및 함수들에 핵심적인 부분들이 간략하게 정리되어 있다.

// Inodes.
//
// An inode describes a single unnamed file. // The inode disk structure holds metadata: the file's type, // its size, the number of links referring to it, and the // list of blocks holding the file's content.
//
// The inodes are laid out sequentially on disk at // sb.startinode. Each inode has a number, indicating its // position on the disk.
//
// The kernel keeps a cache of in-use inodes in memory // to provide a place for synchronizing access // to inodes used by multiple processes. The cached // inodes include book-keeping information that is // not stored on disk: ip->ref and ip->valid.
//
// An inode and its in-memory representation go through a // sequence of states before they can be used by the // rest of the file system code.
//
// * Allocation: an inode is allocated if its type (on disk) // is non-zero. ialloc() allocates, and iput() frees if // the reference and link counts have fallen to zero.
//
// * Referencing in cache: an entry in the inode cache // is free if ip->ref is zero. Otherwise ip->ref tracks // the number of in-memory pointers to the entry (open // files and current directories). iget() finds or // creates a cache entry and increments its ref; iput() // decrements ref.
//
// * Valid: the information (type, size, &c) in an inode // cache entry is only correct when ip->valid is 1. // ilock() reads the inode from // the disk and sets ip->valid, while iput() clears // ip->valid if ip->ref has fallen to zero.
//
// * Locked: file system code may only examine and modify // the information in an inode and its content if it // has first locked the inode.
//
// Thus a typical sequence is: // ip = iget(dev, inum) // ilock(ip) // ... examine and modify ip->xxx ... // iunlock(ip) // iput(ip)
//
// ilock() is separate from iget() so that system calls can // get a long-term reference to an inode (as for an open file) // and only lock it for short periods (e.g., in read()). // The separation also helps avoid deadlock and races during // pathname lookup. iget() increments ip->ref so that the inode // stays cached and pointers to it remain valid.
//
// Many internal file system functions expect the caller to // have locked the inodes involved; this lets callers create // multi-step atomic operations.
//
// The icache.lock spin-lock protects the allocation of icache // entries. Since ip->ref indicates whether an entry is free, // and ip->dev and ip->inum indicate which i-node an entry // holds, one must hold icache.lock while using any of those fields.
//
// An ip->lock sleep-lock protects all ip-> fields other than ref, // dev, and inum. One must hold ip->lock in order to // read or write that inode's ip->valid, ip->size, ip->type, &c.

 

: inode 캐쉬는 총 50개 할당된다. 그리고, `iinit` 함수는 모든 `inode` 캐쉬의 슬립-락을 초기화한다. 그리고, `xv6`의 파일 시스템 메타 정보를 알기 위해서 `superblock`을 읽어들인다. 참고로, `inode` 구조체에서 사용하는 락은 `슬립-락`이다. `sleeplock` 파트에서도 말했지만, `xv6`에서 파일 시스템 관련된 부분은 `슬립-락`을 사용한다. `inode` 캐쉬(icache)는 스핀-락을 사용한다.

// fs.c .... .... struct {   struct spinlock lock;   struct inode inode[NINODE]; // NINODE == 50 } icache; void iinit(int dev) {   int i = 0;      initlock(&icache.lock, "icache");   for(i = 0; i < NINODE; i++) {     initsleeplock(&icache.inode[i].lock, "inode");   }   readsb(dev, &sb);   cprintf("sb: size %d nblocks %d ninodes %d nlog %d logstart %d\   inodestart %d bmap start %d\n", sb.size, sb.nblocks,           sb.ninodes, sb.nlog, sb.logstart, sb.inodestart,           sb.bmapstart); }

 

: `ialloc` 함수는 inode를 할당해주는 함수다. 먼저 `xv6`에서는 inode 관련한 자료 구조가 2가지가 있다. 실제 물리적 디스크에 저장될 때의 포맷인 `struct dinode` 구조체가 있고, 소프트웨어적으로 편의상 이용하는 `struct inode` 구조체가 있다.

// file.h .... .... // in-memory copy of an inode struct inode {   uint dev;           // Device number   uint inum;          // Inode number   int ref;            // Reference count   struct sleeplock lock; // protects everything below here   int valid;          // inode has been read from disk?   short type;         // copy of disk inode   short major;   short minor;   short nlink;   uint size;   uint addrs[NDIRECT+1]; }; .... .... #################################################################################################### // fs.h .... .... struct dinode {   short type;           // File type   short major;          // Major device number (T_DEV only)   short minor;          // Minor device number (T_DEV only)   short nlink;          // Number of links to inode in file system   uint size;            // Size of file (bytes)   uint addrs[NDIRECT+1];   // Data block addresses }; // Inodes per block. #define IPB           (BSIZE / sizeof(struct dinode)) // Block containing inode i #define IBLOCK(i, sb)     ((i) / IPB + sb.inodestart) #################################################################################################### // fs.c .... .... //PAGEBREAK! // Allocate an inode on device dev. // Mark it as allocated by  giving it type type. // Returns an unlocked but allocated and referenced inode. struct inode* ialloc(uint dev, short type) {   int inum;   struct buf *bp;   struct dinode *dip;   for(inum = 1; inum < sb.ninodes; inum++){     bp = bread(dev, IBLOCK(inum, sb));     dip = (struct dinode*)bp->data + inum%IPB;     if(dip->type == 0){  // a free inode       memset(dip, 0, sizeof(*dip));       dip->type = type;       log_write(bp);   // mark it allocated on the disk       brelse(bp);       return iget(dev, inum);     }     brelse(bp);   }   panic("ialloc: no inodes"); }

: `ialloc` 함수에서 제일 먼저 하는 일은 루프를 돌려서, FREE한 inode를 찾는 것이다. 버퍼 캐시에 대한 상세한 내용은 이 글을 참고하자.

 

: `IBLOCK` 매크로 함수는 디스크에 할당된 inode 디스크 섹터 번호를 반환한다. 섹터를 반환하는 구조는 다음과 같다.

(0 / 32) + 32(inode 디스크 시작 번호) = 32
(1 / 32) + 32 = 32
(2 / 32) + 32 = 32
....
(32 / 32) + 32 = 33
(33 / 32) + 32 = 33
....

: 실제 디스크에 저장되는 inode는 `struct dinode` 구조체이다. 이 구조체 크기는 16B이고, 한 섹터는 512B이다. 결국, 한 섹터에 32개의 inode가 저장될 수 있다. inode가 33개가 되면, 32번째 inode(inode는 0번부터 시작)는 두 번째 섹터에 저장되어야 한다. 그리고 inode의 시작 섹터는 앞에 `부트 섹터(1) + 슈퍼 블락(1) + 로그 블락(30)` 블락들을 제외하니 32번 섹터부터 저장이 된다고 보면 된다. `IBLOCK` 매크로 함수가 괄호가 없어서, 연산의 우선위가 헷갈릴 수 있으니, 주의가 필요하다.

IBLOCK(i, sb)     ((i) / IPB + sb.inodestart) == IBLOCK(i, sb)     (((i) / IPB) + sb.inodestart) 

: inode가 저장될 버퍼 캐시를 성공적으로 가져오면, 이제 해당 버퍼 캐시 데이터 영역에 dinode를 할당해야 한다. 

 

: `iget` 함수는 캐쉬된 inode(icache)를 찾아서 반환하거나, 새로운 inode 캐쉬를 생성한다. `1 영역`  으로 표시된 부분이 캐쉬된 inode가 있을 경우, 즉각적으로 해당 inonde를 반환하는 코드다. 여기서 `ip->ref > 0` 조건을 눈 여겨볼 필요가 있다. `ip->ref > 0 && ip->dev == dev && ip->inum == inum` 조건문은 캐쉬된 inode를 찾는 조건인데, 만약 여기서 `ip->ref > 0`가 없다면, 어떻게 될까? 즉, `ip->dev == dev && ip->inum == inum` 조건만으로 캐쉬된 inode를 찾았다고 말할 수 있을까?

// fs.c .... .... // Find the inode with number inum on device dev // and return the in-memory copy. Does not lock // the inode and does not read it from disk. static struct inode* iget(uint dev, uint inum) {   struct inode *ip, *empty;   acquire(&icache.lock);   // Is the inode already cached?   empty = 0;   for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){     if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ // --- 1 영역       ip->ref++;       release(&icache.lock);       return ip;     }     if(empty == 0 && ip->ref == 0)    // Remember empty slot.  // --- 2 영역       empty = ip;   }   // Recycle an inode cache entry.   if(empty == 0) // --- 3 영역     panic("iget: no inodes");   // --- 4 영역   ip = empty;   ip->dev = dev;   ip->inum = inum;   ip->ref = 1;   ip->valid = 0;   release(&icache.lock);   return ip; }

: 소스를 분석해보면 알겠지만, `ip->ref`는 `iget`, `idup`함수에서 증가하고, `iput` 함수에서 감소한다. 그런데, 이런 내용은 누구나 알 수 있는 내용이다. `ip->ref` 변수에 대한 좀 더 기능적이고 의미가 있는 내용이 필요하다. 이럴 때, `xv6`를 만든이의 글을 참조하면 된다. 아래 내용을 보면, 기능적으로 `ip->ref` 변수는 0일 경우, `FREE`를 의미한다고 한다. 그래서, `iget`에서 캐쉬된 inode를 찾는 조건으로 `ip->ref > 0` 가 들어간 것이 이해가 될 것이다.

....
Referencing in cache: an entry in the inode cache is free if `ip->ref` is zero. Otherwise `ip->ref` tracks the number of in-memory pointers to the entry (open files and current directories). `iget()` finds or creates a cache entry and increments its ref; `iput()` decrements ref.
....

- 참고 : https://github.com/mit-pdos/xv6-public/blob/eeb7b415dbcb12cc362d0783e41c3d1f44066b17/fs.c#L188

 

: `if(empty == 0 && ip->ref == 0)` 의 의미는 `혹시나 캐쉬된 inode가 발견되지 않을 경우를 대비해서, 제일 먼저 발견되는 FREE icache 반환해야 겠다` 라는 의미의 조건문이다. 위에서 `ip->ref == 0`의 의미가 FREE한 inode라는 것은 알았다. 여기에, `empty == 0` 조건이 추가되면, `icache에서 FREE한 inode중에서 제일 먼저 발견되는 inode를 반환`의 의미가 된다. 왜냐면, empty 값이 한 번 할당되는 순간 저 조건문는 다시는 들어갈 수 없게 되기 때문이다.

 

:  `3 영역`으로 표시된 부분을 보면, icache가 모두 할당되어 더 이상 할당할 inode가 없음을 의미한다. `xv6`에서 이럴 경우, 패닉이 된다. 나는 이 부분에 대해 좀 고민해 볼 필요가 있다는 생각이든다. 캐쉬가 없다고 패닉? 

 

: `4 영역`으로 표시된 부분에서 제일 중요한 부분은 `ip = empty` 이다. 위의 조건문에서 `empty = ip` 해놓고, 여기서 다시 `ip = empty`를 하는 이유가 뭘까? 만약, 코드가 `4 영역` 까지 왔다면, empty에는 `icache에서 FREE한 inode중에서 제일 먼저 발견되는 inode`가 들어있어야 한다. 그런데, `ip`는 루프를 모두 돌고온 inode다. 즉, `4 영역`에서 들어선  `ip` 변수는 여러 가지 값을 가질 수 있다.

 

0" icache에서 FREE한 inode중에서 제일 마지막에 발견된 inode
1" 캐쉬된 inode는 맞지만, dev와 inum이 일치하지 않는 inode

 

: 다른 값일 수 도 있지만, 핵심은 `icache에서 FREE한 inode중에서 제일 먼저 발견되는 inode` 에 넣겠다는 것이다. 그래서, `4 영역`에 진입하는 시작 부분에 `ip = empty`를 꼭 작성해야 한다. `ip->ref = 1`은 캐쉬가 되었음을 나타내는 표시와 같고, `ip->valid = 0`은 아직 디스크에서 데이터를 읽어오지 않는 상태를 의미한다.

 

: `iupdate`는 인-메모리 inode에 저장되어 있는 데이터를 디스크와 동기화시키는 작업을 한다. `iupdate` 함수위에 주석에서 이미 설명하고 있지만, 대 부분의 파일 시스템 관련 기능들은 캐쉬 및 인-메모리 구조를 갖는다. 왜냐면, 매번 디스크에 변경된 작업 내용을 쓰는 것은 비효율적이기 때문이다. 여기서 `write-through`는 변경 작업들을 메모리에 저장했다가, 특정 조건 및 시그널이 트리거되면 디스크에 동기화하겠다는 뜻이다. `write-back` 이라는 것도 있는데, 이건 메모리에 쓸 때마다 디스크에 동기화하겠다는 뜻이다.

// Copy a modified in-memory inode to disk. // Must be called after every change to an ip->xxx field // that lives on disk, since i-node cache is write-through. // Caller must hold ip->lock. void iupdate(struct inode *ip) {   struct buf *bp;   struct dinode *dip;   bp = bread(ip->dev, IBLOCK(ip->inum, sb)); // --- `1 영역`   dip = (struct dinode*)bp->data + ip->inum%IPB; // --- `2 영역`   dip->type = ip->type;   dip->major = ip->major;   dip->minor = ip->minor;   dip->nlink = ip->nlink;   dip->size = ip->size;   memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));   log_write(bp);   brelse(bp); }

: 인자로 전달받은 inode의 버퍼 캐시가 존재하는지 확인한다. 없다면, 새로운 버퍼 캐시를 전달받게 된다(`1 영역`). 그리고, 전달받은 버퍼 캐시의 데이터 영역에서 자기가 어느 위치에 저장되는지를 알아야한다(`2 영역`). 그리고, 전달받은 inode의 메타 데이터를 디스크에 저장될 dip의 메타 데이터에 복사한다. 그리고 나서 실제 데이터 블락을 복사한다(`memmove(dip->addrs, ip->addrs, sizeof(ip->addrs))`).

 

: 근데, `iupdate` 함수는 왜 만들었을까? `iupdate` 함수가 사용되는 곳을 보면 `itrun`, `iput`이다. 이 함수들의 특징은 인-메모리 inode를 제거하는 함수들이다. 즉, `iupdate`함수는 인-메모리 inode를 제거하지전에 해당 내용을 디스크에 동기화하는 함수라는 뜻이다.

 

: 근데, 앞에서 봤던 icache는 어디가고 직접 inode를 전달하는 것일까? `fs.c` 파일을 보면 알 수 있지만, `fs.c` 파일에 있는 거의 모든 함수가 인자로 `struct inode *ip`를 받고있다. 이게 어디서 오는 것일까? 둘 중 하나다. `ialloc` 혹은 `iget`. `ialloc`은 외부로 노출이 되어 있는 함수이고, `iget`는 내부적으로만 사용이 가능하다. 그리고 `ialloc`은 내부적으로 `iget`을 사용한다. 결국, inode를 사용하고 싶다면, `iget` 함수를 거치지 않고는 불가능하다. `fs.c` 파일에 전역 변수로 `icache`가 있어서, 원한다면, `icache`를 사용해서 inode를 가져올 수 있지만, `xv6`는 그렇게 구현하고 있지는 않다.

 

: 이 내용들을 정리하면, `iupdate` 함수에 들어오는 inode 또한 결국, `iget` 함수를 통해 받은 inode라는 것이다. 위에서도 봤겠지만, `iget` 함수는 내부적으로 `icache`를 사용하고 있다.

 

: `idup` 함수는 `fs.c` 파일 중 가장 간단한 함수다. 

// Increment reference count for ip. // Returns ip to enable ip = idup(ip1) idiom. struct inode* idup(struct inode *ip) {   acquire(&icache.lock);   ip->ref++;   release(&icache.lock);   return ip; }

: `ilock` 함수는 기능적으로 2가지 일을 맡고 있다.

0" 파일 시스템 관련 함수이기 때문에 전달받은 inode에 대해 대한 슬립-락을 획득한다.
1" 만약, 전달받은 inode가 디스크로부터 데이터를 읽어온 적이 한 번도 없다면, 버퍼 캐시에서 inode에 대응하는 데이터를 가져와서 전달받은 인-메모리 inode에 복사한다. 

: 아래 주석에 조금 오해의 소지가 있다. `Reads the inode from 'disk' if necessary.` 문장에서 `disk`는 실제 물리 디스크가 아닌, 버퍼 캐시를 의미한다. 이 부분에 주의하자.

// fs.c .... .... // Lock the given inode. // Reads the inode from disk if necessary. void ilock(struct inode *ip) {   struct buf *bp;   struct dinode *dip;   if(ip == 0 || ip->ref < 1)     panic("ilock");   acquiresleep(&ip->lock);   if(ip->valid == 0){     bp = bread(ip->dev, IBLOCK(ip->inum, sb));     dip = (struct dinode*)bp->data + ip->inum%IPB;     ip->type = dip->type;     ip->major = dip->major;     ip->minor = dip->minor;     ip->nlink = dip->nlink;     ip->size = dip->size;     memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));     brelse(bp);     ip->valid = 1;     if(ip->type == 0)       panic("ilock: no type");   } }

: `iunlock` 함수는 반드시 `ilock` 함수와 한 쌍으로 호출되어야 한다. `sleeplock` 글에서 설명을 했지만, `holdingsleep` 함수는 슬립-락을 점유하지 않은 비정상 프로세스가 동작하는 것을 막는 역할을 한다. `holdingsleep` 함수에서 `PANIC`이 발생했다면, `iunlock` 함수를 호출하기전에 `ilock` 함수를 호출하지 않은 경우다.

// Unlock the given inode. void iunlock(struct inode *ip) {   if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)     panic("iunlock");   releasesleep(&ip->lock); }

: `stati` 함수는 구조가 굉장히 단순하다. 전달받은 inode의 메타 데이터를 전역 변수로 선언되어 있는 `st(struct stat)`에 복사하는 것이다. 이 함수는 파일의 정보를 조회하기 위해 `sys_fstat` 시스템 콜을 호출할 경우, 내부적으로 호출되는 함수다.

 

: 그런데, 사실 `stati` 함수를 보고 약간 멘붕이왔다. `struct stat`에 `dev` 필드를 보면, `File system`s disk device`라고 되어있다. `struct inode`의 `dev`에는 주석으로 `Device number`라고 써있다. 지금 이 부분이 멘붕인 이유는 `dev`가 디스크 드라이브 번호를 의마하는 것인가에 대한 확신이 없기 때문이다. 여태까지, `xv6`에서 파일 시스템 관련 자료 구조에서 나오는 모든 `dev` 필드를 ID 같은 것이라 생각하고 글을 썼는데, 수정해야 될 지도 모르겠다.

// stat.h .... .... struct stat {   short type;  // Type of file   int dev;     // File system's disk device   uint ino;    // Inode number   short nlink; // Number of links to file   uint size;   // Size of file in bytes }; .... .... #################################################################################################### // fs.c .... .... // Copy stat information from inode. // Caller must hold ip->lock. void stati(struct inode *ip, struct stat *st) {   st->dev = ip->dev;   st->ino = ip->inum;   st->type = ip->type;   st->nlink = ip->nlink;   st->size = ip->size; }

: `bmap` 함수는 inode 관련 작업에서 굉장히 중요한 역할을 한다. 이 함수는 inode가 가지고 있는 `n` 번째 데이터 블락 주소를 반환하는 역할을 한다. 

//PAGEBREAK! // Inode content // // The content (data) associated with each inode is stored // in blocks on the disk. The first NDIRECT block numbers // are listed in ip->addrs[].  The next NINDIRECT blocks are // listed in block ip->addrs[NDIRECT]. // Return the disk block address of the nth block in inode ip. // If there is no such block, bmap allocates one. static uint bmap(struct inode *ip, uint bn) {   uint addr, *a;   struct buf *bp;   if(bn < NDIRECT){     if((addr = ip->addrs[bn]) == 0)       ip->addrs[bn] = addr = balloc(ip->dev);     return addr;   }   bn -= NDIRECT;   if(bn < NINDIRECT){     // Load indirect block, allocating if necessary.     if((addr = ip->addrs[NDIRECT]) == 0)       ip->addrs[NDIRECT] = addr = balloc(ip->dev);     bp = bread(ip->dev, addr);     a = (uint*)bp->data;     if((addr = a[bn]) == 0){       a[bn] = addr = balloc(ip->dev);       log_write(bp);     }     brelse(bp);     return addr;   }   panic("bmap: out of range"); }

: 먼저 `bmap` 함수를 그냥 맨땅에 분석하기는 난이도가 있다. 그래서, 먼저 `xv6` 에서 `bmap` 함수에 대해 어떻게 설명하는지 알아본다.

: `struct dinode`에는 `uint addrs[NDIRECT+1]` 이라는 필드가 있다. 이 필드에는 inode가 가리키는 파일의 데이터가 저장이 된다. 그런데, 이 `addrs` 필드는 `DIRECT`와 `INDIRECT`로 나뉘어져 있다. `DIRECT` 필드는 위 그림에서 볼 수 있다시피, 직접 블락 데이터에 직접 접근할 수 있는 필드를 의미한다. `DIRECT` 필드는 총 12개로 이루어져 있다. 그리고, `INDIRECT` 필드는 128개의 데이터 블락을 저장하고 있는 주소를 의미하는 필드다. 위 그림에서 볼 수 있다시피, `INDIRECT`라는 필드는 또 다른 데이터 블락 공간을 가리키고 있는 것을 볼 수 있다. `addrs`에서 13번째 필드가 `INDIRECT`가 된다.

The on-disk inode structure, `struct dinode`, contains a size and an array of block numbers (see Figure 6-3). The inode data is found in the blocks listed in the `dinode’s addrs` array. The first `NDIRECT` blocks of data are listed in the first `NDIRECT` entries in the array; these blocks are called `direct blocks`. The next `NINDIRECT` blocks of data are listed not in the inode but in a data block called the `indirect block`. The last entry in the addrs array gives the address of the indirect block. Thus the first 6 kB (`NDIRECT×BSIZE`) bytes of a file can be loaded from blocks listed in the inode, while the next 64kB (`NINDIRECT×BSIZE`) bytes can only be loaded after consulting the indirect block. This is a good on-disk representation but a complex one for clients. The function bmap manages the representation so that higher-level routines such as `readi` and `writei`, which we will see shortly. Bmap returns the disk block number of the bn’th data block for the inode ip. If ip does not have such a block yet, bmap allocates one.

The function bmap (5410) begins by picking off the easy case: the first NDIRECT blocks are listed in the inode itself (5415-5419). The next NINDIRECT blocks are listed in the indirect block at ip->addrs[NDIRECT]. Bmap reads the indirect block (5426) and then reads a block number from the right position within the block (5427). If the block number exceeds `NDIRECT+NINDIRECT`, bmap panics; writei contains the check that prevents this from happening (5566).
....

- 참고 : Code: Inode content

: `bmap`은 inode의 핵심 함수다. 이 함수를 통해 특정 inode를 전달했을 때, 해당 inode와 연결된 모든 데이터를 추출해 낼 수 있다. 먼저, `bmap` 함수는 전달받은 `bn`의 크기에 `직접` 영역으로 처리할지, `간적` 영역으로 처리할지 결정해야 한다. 12보다 작을 경우, `직접`영역에서 처리한다. 12보다 크거나 같을 경우, `간접`영역에서 처리한다. 여기서 `bn -= NDIRECT`의 값은 다음과 같이 된다.

" bn = 1 -> DIRECT 1 -> Successd
" bn = 4 -> DIRECT 4 -> Successd
....
" bn = 12 -> INDIRECT 0 -> Successd
" bn = 13 -> INDIRECT 1 -> Successd
....
" bn = 139 -> INDIRECT 127 -> Successd
" bn = 140 -> INDIRECT 128 -> Failed

: 그리고 `ip->addrs[NDIRECT] = addr = balloc(ip->dev)` 를 통해서 `간접`영역에 대한 주소를 받게 된다. 이 영역은 128개의 새로운 주소들이 존재한다. 간적 영역에 접근하는 방법은 아래의 순서를 따른다.

0" bp = bread(ip->dev, addr)
1" a = (uint*)bp->data
2" a[bn]

: 위에서 `addr` 값은 주소가 아니다. `unsigned int` 데이터 타입으로 섹터 번호가 할당된다. 그리고, addr과 `ip->addrs[NDIRECT]`이 같다는 것을 알아야 한다. 즉, `bmap`에서 `INDIRECT`를 검사하는 조건문안에서 `addr`은 inode의 간접 영역의 시작 주소 번호를 의미한다. `a`는 포인터 타입의 변수다. 그래서, `a = (uint*)bp->data`를 통해서 `a[bn]`처럼 사용하면, 128개의 간접 영역에 접근할 수 가 있다. 

 

: `balloc`후에 `bread`를 진행하는 것은 `balloc` 함수를 통해 FREE한 디스크 섹터를 하나 할당받고, 해당 디스크 섹터를 `bread` 함수를 통해서 캐쉬하는 것이다. 그런데, 이 때 중요한 점은 마치 `balloc` 함수에서 디스크 섹터를 할당해줄 것 같지만, 실제로 이 함수에서는 단지 FREE한 디스크 섹터 번호를 반환해준다. 

 

: `balloc` 함수는 실제 디스크 블락을 할당해주는 함수다. 비트맵을 통해서 디스크 블락을 관리한다.

#################################################################################################### // mkfs.c .... .... int nbitmap = FSSIZE/(BSIZE*8) + 1; .... sb.size = xint(FSSIZE); .... .... #################################################################################################### // param.h .... .... #define FSSIZE       1000  // size of file system in blocks .... .... #################################################################################################### // fs.h .... .... #define BSIZE 512  // block size // Bitmap bits per block #define BPB           (BSIZE*8) .... // Block of free map containing bit for block b #define BBLOCK(b, sb) (b/BPB + sb.bmapstart) .... .... #################################################################################################### // fs.c .... .... // Allocate a zeroed disk block. static uint balloc(uint dev) {   int b, bi, m;   struct buf *bp;   bp = 0;   for(b = 0; b < sb.size; b += BPB){     bp = bread(dev, BBLOCK(b, sb));     for(bi = 0; bi < BPB && b + bi < sb.size; bi++){       m = 1 << (bi % 8);       if((bp->data[bi/8] & m) == 0){  // Is block free?         bp->data[bi/8] |= m;  // Mark block in use.         log_write(bp);         brelse(bp);         bzero(dev, b + bi);         return b + bi;       }     }     brelse(bp);   }   panic("balloc: out of blocks"); }

: `xv6`는 전체 디스크 섹터 개수를 1000개로 제한한다(FSSIZE = 1000). 그러므로, 디스크 블록들을 관리하는 비트맵 메타 데이터 블락 개수는 1개면 충분하다(int nbitmap = FSSIZE/(BSIZE*8) + 1). 왜냐면, 블록(섹터) 한개면 512B이고, 이걸 비트로 치면 4096개이기 때문이다. 즉, 비트맵을 사용하면 한 섹터로 4096개의 섹터를 관리할 수 있다.

 

: `balloc` 함수의 바깥쪽 루프와 안쪽 루프는 역할이 나눠져 있다. 바깥쪽 루프에서 비트맵 메타 데이터 관리를 위한 섹터를 1개씩 꺼내오면, 안쪽에서는 해당 섹터의 모든 비트를 검사한다. 즉, 4096개의 섹터를 검사한다. 그런데, `xv6`에서는 전체 섹터 개수가 1000개 밖에 안되서 바깥쪽 루프문의 의미가 없다. 왜냐면, 한 개 섹터면(4096) `xv6`에서 지원하는 모든 섹터(1000)를 검사할 수 있기 때문이다. 안쪽 루프에서 `bi < BPB` 조건이 아닌, `b + bi < sb.size(1000)` 조건에 걸려서 루프를 빠져나오게 될 것이다. 거기다가, `1000 / 8 = 125`로, 할당받은 모든 섹터를 사용한 것도 아니다. 즉, 4096개의 섹터를 검사할 수 있는데, 1000개까지만 검사하고 끝내는 것이다. 

 

: 위에서 `8`로 나누는 이유는 `xv6`에서 비트맵 단위가 1 바이트이기 때문이다. 비트맵 단위는 대개 사용하는 데이터 타입에 의존하는 경우가 많다. 위에서 비트맵 단위는 `buf->data` 에 의존하는데, 여기서 `buf->data`가 `unsigned char`형이다. 비트맵은 메타 데이터 관리를 위해서 많이 사용되는 자료 구조이기 때문에, 자주 접해보는 것이 좋다.

 

: 그리고 나서, `bp->data[bi/8] |= m` 을 통해 비어있는 데이터 블락을 찾으면, 비트맵에 사용중이라는 체크를 한다. `bzero` 함수는 전달받은 주소에서 512B 만큼을 0으로 초기화하는 함수다. 그리고, 최종적으로 `b + bi`을 리턴하는 이유는 `balloc` 함수가 디스크 섹터 번호를 반환를 하기 때문이다.

 

: `bfree` 함수는 전달받은 섹터 번호에 대응하는 디스크 상태를 FREE로 변경하는 함수다.

// fs.c .... .... // Free a disk block. static void bfree(int dev, uint b) {   struct buf *bp;   int bi, m;   bp = bread(dev, BBLOCK(b, sb));   bi = b % BPB;   m = 1 << (bi % 8);   if((bp->data[bi/8] & m) == 0)     panic("freeing free block");   bp->data[bi/8] &= ~m;   log_write(bp);   brelse(bp); }

: 먼저 전달받은 섹터 번호를 `BBLOCK` 매크로에 전달해서 비트맵 메타 데이터 블록을 반환받는다. 그리고 `b % BPB`를 통해서 섹터내에서 비트맵 인덱스를 찾아낸다. 예를 들어서, `xv6`에서 전체 섹터 데이터 섹터가 20000개 라고 가정하자. 그리고, 비트맵 관리를 위해 4개의 섹터를 할당받았다고 치자. 그렇면, 한 섹터 당 4096개의 섹터를 관리할 수 있으니, 4개면 총 16384개의 섹터를 관리할 수 있게 된다. 만약, 사용자가 9251번 섹터를 할당받았다. 그리고, 시간이 흘러서 다시 해제하기 위해 `bfree` 함수를 호출했다고 치자. 이 때, 9521을 전달받았다. 그렇면, `BBLOCK(b, sb)` 매크로 함수는 무엇을 반환할까? `BBLOCK(b, sb)` 매크로 함수에서 `sb.bmapstart` 을 더하는 과정이 없다면, `2`를 반환할 것이다. 즉, 번호를 2번째 비트맵 메타 데이터 섹터를 반환받게 된다. 왜냐면, `4096 + 4096 + 1329 = 9521` 이기 때문에, 앞에 0번, 1번 섹터에서는 FREE한 섹터가 없고, 2번에서 1329번 섹터부터가 FREE한 섹터일 것이다.

 

: `bi = b % BPB` 의 의미는 뭘까? 블록 내에서 오프셋을 의미한다. 위에서 `1329` 라는 값은 9521을 4096으로 나눴을 때의 나머지다. 즉, 2번째 섹터에서 몇 번째 블록인지를 알아내야 하기에 나머지 연산이 사용되었다. 나머지 과정들은 `balloc` 함수에서와 크게 다르지 않다.

 

: `writei` 및 `readi` 함수는 inode에 저장되어 있는 데이터 블락에서 데이터를 읽거나 쓰는 함수들이다. 파라미터는 다음과 같다.

0" struct inode *ip : 해당 inode를/에 읽거나 쓴다.
1" src or dst : 읽거나 쓸 내용.
2" off : inode의 데이터 블락의 시작 위치를 나타낸다. 즉, 어디서부터 읽을 건지, 어디서부터 쓸건지를 나타낸다.
3" n : 읽거나 쓸 사이즈를 의미한다.

: 2개의 함수가 비슷한 구조를 나타내기 때문에 같이 분석한다. 먼저, 실제로 어떻게 inode에서 어떻게 데이터를 읽는지, 어떻게 데이터를 쓰는지 알아보자.

// fs.c .... .... //PAGEBREAK! // Read data from inode. // Caller must hold ip->lock. int readi(struct inode *ip, char *dst, uint off, uint n) { uint tot, m;   struct buf *bp;   if(ip->type == T_DEV){     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)       return -1;     return devsw[ip->major].read(ip, dst, n);   }   if(off > ip->size || off + n < off)     return -1;   if(off + n > ip->size)     n = ip->size - off;   for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ // --- 4r     bp = bread(ip->dev, bmap(ip, off/BSIZE)); // --- 1r     m = min(n - tot, BSIZE - off%BSIZE); // --- 2r     memmove(dst, bp->data + off%BSIZE, m); // --- 3r     brelse(bp);   }   return n; } .... .... #################################################################################################### // fs.c .... .... // PAGEBREAK! // Write data to inode. // Caller must hold ip->lock. int writei(struct inode *ip, char *src, uint off, uint n) {   uint tot, m;   struct buf *bp;   if(ip->type == T_DEV){     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)       return -1;     return devsw[ip->major].write(ip, src, n);   }   if(off > ip->size || off + n < off)     return -1;   if(off + n > MAXFILE*BSIZE)     return -1;   for(tot=0; tot<n; tot+=m, off+=m, src+=m){ // --- 4w     bp = bread(ip->dev, bmap(ip, off/BSIZE)); // --- 1w     m = min(n - tot, BSIZE - off%BSIZE); // --- 2w     memmove(bp->data + off%BSIZE, src, m); // --- 3w      log_write(bp);     brelse(bp);   }   if(n > 0 && off > ip->size){     ip->size = off;     iupdate(ip);   }   return n; } .... ....

: 먼저 `writei`를 분석해보자. `1w` 영역을 보면, `bmap` 함수에 `off/BSIZE`를 전달하고 있다. `bmap` 함수는 전달받은 inode에서 n 번째 데이터 블락을 반환한다. `writei` 함수에서 `off`의 단위는 바이트다. 그래서, 만약 `off`의 값이 5267 라면, 이 의미는 10번째 데이터 블락(5267/512)의 147번 바이트부터 쓰겠다는 뜻이다. 그래서 `1w` 영역은 먼저, `off`를 통해서 write를 해야하는 데이터 블락을 받게된다. 그리고, `2w` 영역은 `1w` 영역에서 꺼내온 데이터 블락에 실제 얼마나 데이터를 쓸 수 있는지를 판단하는 부분이다. 위의 예시를 재사용하자. 만약 `off`의 값이 5267 라면, 10번째 데이터 블락(5267/512)의 147번 바이트부터 쓰겠다는 뜻이다. 그런데, 블락의 크기는 512다. 즉, 147을 start로 잡는다면, `512 - 147 = 365` 길이만큼만 데이터를 쓸 수 있다. 그 이상 쓰게되면 당연히, 메모리 충돌이 발생한다. 결국, `2w` 영역은 실제 데이터를 쓸 수 있는 길이를 정하는 코드라고 보면된다. 아마, 초기에는 `BSIZE - off%BSIZE`가 m에 할당되겠지만, 마지막에는 m의 값이 `n - tot`이 될 것이다. 위의 예시를 재사용하자.

" `n = 0x4000 and off = 5267`를 전제한다.
첫 번째 루프" n - tot = 4000, BSIZE - off%BSIZE = 365 -> tot = 0 , off = 5267, m = 365
두 번째 루프" n - tot = 4000, BSIZE - off%BSIZE = 512 -> tot = 365 , off = 5632, m = 512
세 번째 루프" n - tot = 4000, BSIZE - off%BSIZE = 512 -> tot = 877 , off = 6144, m = 512
....
여덝 번째 루프" n - tot = 4000, BSIZE - off%BSIZE = 512 -> tot = 3949 , off = 9216, m = 51

: 조건을 `n = 0x4000 and off = 5267`로 가정하고 진행했을 때, 맨 마지막 루프를 제외하고는 최소값을 선택되는 코드는 `BSIZE - off%BSIZE`이다. 그리고 마지막에 `n - tot`가 선택된다. 이렇게 되는 이유는 위에서 말했다시피, `메모리 충돌`이 발생시키지 않기 위해서다.

 

: 그리고나서, `3w` 영역을 보면, `m` 값만큼 `bp->data + off%BSIZE`에 쓰고 있다. 핵심적인 부분들을 살펴봤으니, 이제 나머지 부분을 살펴보자. 먼저 예외 처리 부분부터 살펴보자.

 

: `off > ip->size || off + n < off` 이 코드의 의미는 다음과 같다.

0" `off > ip->size` : 말 그대로, 파일에 데이터를 쓸 시작 주소가 파일의 마지막 주소보다 클 경우, 당연히 에러다. 그런데, 주의점은 이 예외 처리가 유효할 수 있는 것은 `off`가 0부터 시작한다는 전제가 있기 때문이다. 만약에, `off`가 모든 inode에 대한 절대적인 주소라면, 저런 조건문은 나올 수 없다. 

1" `off + n < off` : 직관적으로 와닿기가 어려운 예외 처리문이다. 왜냐면, `이해는 되지만 이런 경우가 실제로 존재할까?` 에 대한 부분이 있기 때문이다. 이식은 수학에서 `부등식의 성질`을 적용하면 조금 더 이해하기가 쉽다. 양변에 `off`를 빼보자. 그렇면 `n < 0`이 된다. 즉, 전달된 사이즈가 0이면 안된다는 것이다. 그런데, 정말 프로그래밍에서 `off + n < off` == `n < 0`이 성립할까? 

 

: 마지막으로, inode의 타입 중 `디바이스 타입`에 대해 알아보자. 이 내용은 `xv6` 문서를 먼저 살펴보자. 유닉스 계열의 운영 체제에서는 모든게 파일이다보니, 디바이스도 하나의 파일로 본다. 그래서 유닉스 계열의 운영체제에 존재하는 모든 개체는 `inode`를 가지고있다. 이렇게, 디바이스 타입의 inode는 실제 데이터 블락은 존재하지 않는다. 단지, 이 커널 디바이스들과 통신할 수 있는 인터페이스만 존재한다. 그래서 만약, open 함수를 통해서 특정 디바이스 파일을 열면, 특정 데이터 블락과 연결되는게 아니라, 커널 디바이스와 연결된다.

`Mknod` creates a file in the file system, but the file has no contents. Instead, the file’s metadata marks it as a `device file` and records the major and minor device numbers (the two arguments to mknod), which uniquely identify a kernel device. When a process later opens the file, the kernel diverts read and write system calls to the kernel device implementation instead of passing them to the file system.
....

Init (8510) creates a new console device file if needed and then opens it as file descriptors 0, 1, and 2.
....

Both `readi` and `writei` begin by checking for `ip->type == T_DEV`. This case handles special devices whose data does not live in the file system; we will return to this case in the file descriptor layer.
....

- 참고 : xv6 - DRAFT as of September 4, 2018

: `xv6`에서는 디바이스 파일로 등록되는 디바이스는 콘솔 디바이스밖에 없다. 등록이나 호출하는 과정자체가 어려운 부분이 없기, 때문에 나중에 유저 레벨 시스템 콜에서 좀 더 자세히 다루도록 하겠다.

// file.h .... .... // table mapping major device number to // device functions struct devsw {   int (*read)(struct inode*, char*, int);   int (*write)(struct inode*, char*, int); }; extern struct devsw devsw[]; #define CONSOLE 1 .... .... #################################################################################################### // file.c .... struct devsw devsw[NDEV]; // NDEV = 10 .... #################################################################################################### // console.c .... .... void consoleinit(void) {   initlock(&cons.lock, "console");   devsw[CONSOLE].write = consolewrite;   devsw[CONSOLE].read = consoleread;   cons.locking = 1;   ioapicenable(IRQ_KBD, 0); }

: 이제 inode 관련 마지막 함수로 `itrunc`, `iput`에 대해 살펴보자. 먼저 `itrunc` 함수를 살펴본다. 

 

: `itrunc` 함수는 인자로 전달된 inode에 연결된 모든 데이터 블락과의 연결을 끊는 함수다. 그런데, 이 함수의 기능을 아는 것도 중요하지만, 이 함수가 호출되는 조건이 더 중요하다. 아래 주석은 다음과 같이 언급하고 있다.

0" 디렉토리 엔트리가 이 inode를 참조하고 있지 않을 경우 
1" 이 inode를 참조하고 있는 `인-메모리` open file 이나 디렉토리가 없을 경우

: 위의 2개의 조건이 모두 성립되어야 `itrunc` 함수를 호출할 수 있다. 먼저, 2번째 조건은 얼핏 이해가간다. 현재, 메모리에 올라와 있는 개체중에서 이 inode를 참조하고 있다면, 당연히 제거하면 안된다. 그런데, 1번째 조건이 조금 애매하다. 저기서 말하는 디렉토리 엔트리는 디스크에 있는 걸까? `링크`와 `참조`는 다른 의미인가?

 

: 소스 분석전 문서도 한 번 살펴보자. 문서에서는 `itrunc` 함수에 대해, 특정 inode에 연결된 모든 파일 블락(데이터 블락)들을 모두 FREE한다고 설명되어 있다.

`itrunc` frees a file’s blocks, resetting the inode’s size to zero. `Itrunc` (5456) starts by freeing the `direct blocks` (5462-5467), then the ones listed in the indirect block (5472- 5475), and finally the `indirect block` itself (5477-5478).
....

`Iput` calls `itrunc` to truncate the file to zero bytes, freeing the data blocks; sets the inode type to 0 (unallocated); and writes the inode to disk (5366).
....

- 참고 : xv6 - DRAFT as of September 4, 2018

 

: 실제 소스를 보면, 정말로 별개 없다. 전달받은 inode에 연결되어 있는 데이터 블락들을 모두 제거한다. 먼저, `DIRECT` 데이터 블락들과의 연결을 끊는다. 그리고, `INDIRECT` 데이터 블락들이 존재할 경우, 그것도 끊는다. `itrunc` 함수는 `static` 함수이기 때문에, 내부에서만 호출되는 함수다. 이 함수를 호출하는 곳은 `iput` 함수이다. 즉, `iput` 함수에서 `itrunc` 함수의 호출 조건을 만들어 준다고 볼 수 있다.

// fs.c .... .... // Truncate inode (discard contents). // Only called when the inode has no links // to it (no directory entries referring to it) // and has no in-memory reference to it (is // not an open file or current directory). static void itrunc(struct inode *ip) {   int i, j;   struct buf *bp;   uint *a;   for(i = 0; i < NDIRECT; i++){     if(ip->addrs[i]){       bfree(ip->dev, ip->addrs[i]);       ip->addrs[i] = 0;     }   }   if(ip->addrs[NDIRECT]){     bp = bread(ip->dev, ip->addrs[NDIRECT]);     a = (uint*)bp->data;     for(j = 0; j < NINDIRECT; j++){       if(a[j])         bfree(ip->dev, a[j]);     }     brelse(bp);     bfree(ip->dev, ip->addrs[NDIRECT]);     ip->addrs[NDIRECT] = 0;   }   ip->size = 0;   iupdate(ip); }

 

: `iput` 함수는 

// Drop a reference to an in-memory inode. // If that was the last reference, the inode cache entry can // be recycled. // If that was the last reference and the inode has no links // to it, free the inode (and its content) on disk. // All calls to iput() must be inside a transaction in // case it has to free the inode. void iput(struct inode *ip) {   acquiresleep(&ip->lock);   if(ip->valid && ip->nlink == 0){     acquire(&icache.lock);     int r = ip->ref;     release(&icache.lock);     if(r == 1){       // inode has no links and no other references: truncate and free.       itrunc(ip);       ip->type = 0;       iupdate(ip);       ip->valid = 0;     }   }   releasesleep(&ip->lock);   acquire(&icache.lock);   ip->ref--;   release(&icache.lock); }