apply RLU in bio.c

[MadPlayer]

#include "types.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "buf.h"
#include "rlu.h"
#include "proc.h"

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");
  RLU_INIT();

  // Create linked list of buffers
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    b->dev = -1;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

// Look through buffer cache for sector on device dev.
// If not found, allocate fresh block.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint sector)
{
  struct buf *b, *prev, *next;

  RLU_READER_LOCK(proc->self);

 loop:
  // Try for cached block.
  for(b = (struct buf *)RLU_DEREF(proc->self, (bcache.head.next));
      b != RLU_DEREF(proc->self, (&bcache.head));
      b = (struct buf *)RLU_DEREF(proc->self, (b->next)))
    {
      if(b->dev == dev && b->sector == sector)
        {
          if(!(b->flags & B_BUSY))
            {
              prev = RLU_DEREF(proc->self, b->prev);
              next = RLU_DEREF(proc->self, b->next);

              if (!RLU_TRY_LOCK(proc->self, &b) &&
                  !RLU_TRY_LOCK(proc->self, &prev) &&
                  !RLU_TRY_LOCK(proc->self, &next))
                {
                  RLU_ABORT(proc->self);
                  goto loop;
                }
              struct buf *new_b = rlu_new_node();
              *new_b = *b;
              new_b->flags |= B_BUSY;
              RLU_ASSIGN_PTR(proc->self, &prev->next, new_b);
              RLU_ASSIGN_PTR(proc->self, &next->prev, new_b);
              RLU_FREE(proc->self, b);

              RLU_READER_UNLOCK(proc->self);
              return new_b;
            }
          goto loop;
        }
    }

  // Allocate fresh block.
 restart:
  for(b = (struct buf *)RLU_DEREF(proc->self, (bcache.head.prev));
      b != RLU_DEREF(proc->self, (&bcache.head));
      b = RLU_DEREF(proc->self, (b->prev)))
    {
      if((b->flags & B_BUSY) == 0)
        {
          prev = RLU_DEREF(proc->self, b->prev);
          next = RLU_DEREF(proc->self, b->next);

          if (!RLU_TRY_LOCK(proc->self, &b) &&
              !RLU_TRY_LOCK(proc->self, &prev) &&
              !RLU_TRY_LOCK(proc->self, &next))
            {
              RLU_ABORT(proc->self);
              goto restart;
            }
          struct buf *new_b = rlu_new_node();
          *new_b = *b;
          new_b->dev = dev;
          new_b->sector = sector;
          new_b->flags = B_BUSY;
          RLU_ASSIGN_PTR(proc->self, &prev->next, new_b);
          RLU_ASSIGN_PTR(proc->self, &next->prev, new_b);
          RLU_FREE(proc->self, b);

          RLU_READER_UNLOCK(proc->self);
          return new_b;
        }
    }
  panic("bget: no buffers");
}

// Return a B_BUSY buf with the contents of the indicated disk sector.
struct buf*
bread(uint dev, uint sector)
{
  struct buf *b;

  b = bget(dev, sector);
  if(!(b->flags & B_VALID))
    iderw(b);
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if((b->flags & B_BUSY) == 0)
    panic("bwrite");
  b->flags |= B_DIRTY;
  iderw(b);
}

// Release the buffer b.
void
brelse(struct buf *b)
{
  struct buf *prev, *next, *head_p, *head_next;

  RLU_READER_LOCK(proc->self);

  if((b->flags & B_BUSY) == 0)
    panic("brelse");

 restart:
  prev = RLU_DEREF(proc->self, b->prev);
  next = RLU_DEREF(proc->self, b->next);

  if (!RLU_TRY_LOCK(proc->self, &prev) &&
      !RLU_TRY_LOCK(proc->self, &next))
    {
      RLU_ABORT(proc->self);
      goto restart;
    }

  /* remove from list */
  RLU_ASSIGN_PTR(proc->self, &next->prev, prev);
  RLU_ASSIGN_PTR(proc->self, &prev->next, next);

 restart2:
  head_p = RLU_DEREF(proc->self, &bcache.head);
  head_next = RLU_DEREF(proc->self, bcache.head.next);

  if (!RLU_TRY_LOCK(proc->self, &head_p) &&
      !RLU_TRY_LOCK(proc->self, &head_next))
    {
      RLU_ABORT(proc->self);
      goto restart2;
    }

  struct buf *new_b = rlu_new_node();
  *new_b = *b;

  /* insert b into tail of list */
  new_b->next = bcache.head.next;
  new_b->prev = &bcache.head;
  new_b->flags &= ~B_BUSY;
  RLU_ASSIGN_PTR(proc->self, &head_next->prev, new_b);
  RLU_ASSIGN_PTR(proc->self, &head_p->next, new_b);
  RLU_FREE(proc->self, b);

  RLU_READER_UNLOCK(proc->self);
}

적용하면서 한 가정들입니다.

1. self는 rlu_thread data _t* 입니다.
2. 모든 thread는 시스템이 시작할때 rlu thread init 및 register를 수행했습니다.
3. rlu_new_node 는 적절한 방법으로 struct buf를 할당합니다.

proc 은 PCB 입니다. self는 rlu_thread_data_t* 입니다.

[bigsys-gnu]

실제 bio.c 에서 하는 동작이 복잡하진 않으니 해당 코드를 Linux user level 에서 테스트 해볼까요? RLU API 사용과 컴파일 방법은 bench.c에서 참고할 수 있으니.

[bigsys-gnu]

방금 논의했듯이, rlu/mv-rlu 실행을 하나씩 확인하는게 좋으니 xv6 user level benchmark에 먼저 적용하고 다음 kernel level로 넘어옵시다.

• 확인사항
  • bget( )함수 내 sleep( ) 없어짐으로 생기는 성능 영향
  • mv-rlu 적용의 경우, b_read( ) 연산은 blocking 없이 동시 수행되는가?
  • B_BUSY flag로 인한 동시성 영향

[MadPlayer]

• sleep sleep을 그대로 두는 대신 read critical section을 해제하고 sleep한 후 다시 시도할 때 read critical section으로 진입하는 것이 좋을 것 같습니다. sleep 하는 이유가 자신이 원하는 buffer cache가 이미 존재해서 다른 프로세스가 사용을 그만둘때까지 기다리는 것인데 만약 read critical section에서 sleep한다면 다시 wakeup 한 후에도 stale data를 읽게 되어 여전히 사용할 수 없을 것입니다.

[MadPlayer]

• B_BUSY flag 기존에 bio.c에 있던 주석입니다. // Buffer cache. // // The buffer cache is a linked list of buf structures holding // cached copies of disk block contents. Caching disk blocks // in memory reduces the number of disk reads and also provides // a synchronization point for disk blocks used by multiple processes. // // Interface: // To get a buffer for a particular disk block, call bread. // After changing buffer data, call bwrite to flush it to disk. // When done with the buffer, call brelse. // Do not use the buffer after calling brelse. // Only one process at a time can use a buffer, // so do not keep them longer than necessary. // // The implementation uses three state flags internally: // B_BUSY: the block has been returned from bread // and has not been passed back to brelse.
  // B_VALID: the buffer data has been initialized // with the associated disk block contents. // B_DIRTY: the buffer data has been modified // and needs to be written to disk.

여기에 보면 오직 하나의 프로세스만 특정 cache를 사용할 수 있다고 합니다.

[MadPlayer]

xv6 관련 이슈이므로 닫겠습니다.