// 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 write 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.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

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

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;

#define NLOCK_BUCKETS 13
// #define ORIGINAL
struct spinlock hash_locks[NLOCK_BUCKETS];
static char lock_names [NLOCK_BUCKETS][20];

struct hash_tbl {
  struct buf* buf;
  struct hash_tbl *next;
} hash_tbl;

struct hash_tbl* hash_entry[NLOCK_BUCKETS];
struct hash_tbl hash_tbls[NBUF];

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");
  for (int i = 0; i < NLOCK_BUCKETS; ++ i) {
    snprintf(lock_names[i], 20, "bcache.lk%d", i);
    initlock(&hash_locks[i], lock_names[i]);
    hash_entry[i] = 0;
  }
  for (int i = 0; i < NBUF; ++ i) {
    hash_tbls[i].buf = &bcache.buf[i];
    hash_tbls[i].next = 0;
  }
  // 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;
    initsleeplock(&b->lock, "buffer");
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

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

  // acquire(&bcache.lock);
#ifndef ORIGINAL
  int bucket = blockno % NLOCK_BUCKETS;
  acquire(&hash_locks[bucket]);
  struct hash_tbl* h = hash_entry[bucket];
  struct hash_tbl* ph = 0;
  while (h != 0) {
    if (h->buf->dev == dev && h->buf->blockno == blockno) {
      b = h->buf;
      b->refcnt ++;
      release(&hash_locks[bucket]);
      // release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
    h = h->next;
  }
  release(&hash_locks[bucket]); 
  // release the unfound bucket, or there'll be deadlock
  acquire(&bcache.lock);
  // after bcache.lock is aquired, only b->refcnt maybe out of our control
  //    so, have to aquire hash_locks[victim_bucket] before test refcnt
  for(int i = 0; i < NBUF; ++ i){
    b = &bcache.buf[i];
    int victim_bucket = b->blockno % NLOCK_BUCKETS;
    acquire(&hash_locks[victim_bucket]);
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      // try to release hash entry from the old bucket
      h = hash_entry[victim_bucket];
      ph = 0;
      while (h != 0) {
        if (h->buf->dev == b->dev && h->buf->blockno == b->blockno) {
          if (ph) ph->next = h->next;
          else hash_entry[victim_bucket] = h->next;
          break;
        }
        ph = h;
        h = h->next;
      }
      release(&hash_locks[victim_bucket]);
      release(&bcache.lock);
      // this should avoid deadlock and meanwhile guard the hashtable
      // because after b is set, the only thing we need is hashtable rather than buf attributes
      h = &hash_tbls[i];
      acquire(&hash_locks[bucket]);
      h->next = hash_entry[bucket];
      hash_entry[bucket] = h;
      release(&hash_locks[bucket]);
      acquiresleep(&b->lock);
      return b;
    }
    release(&hash_locks[victim_bucket]);
  }
#else
  // Is the block already cached?
  // for(b = bcache.head.next; b != &bcache.head; b = b->next){
  for (b = &bcache.buf[0]; b < &bcache.buf[NBUF]; ++ b) {
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  // for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
  for(b = &bcache.buf[0]; b < &bcache.buf[NBUF]; ++ b){
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
#endif
  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

// if you use bcache lock, test0 fails without doubt
// the reason why this works is that, whenever b->refcnt is written or read
//    its 'hash_locks[H(b->blockno)]' will always been locked
// the reason why b->blockno is valid is that, only when refcnt==0 could this field be written
//    but here it must be non-zero before lock aquired
  int bucket = b->blockno % NLOCK_BUCKETS;
  acquire(&hash_locks[bucket]);
  b->refcnt--;
  // if (b->refcnt == 0) {
  //   // no one is waiting for it.
  //   b->next->prev = b->prev;
  //   b->prev->next = b->next;
  //   b->next = bcache.head.next;
  //   b->prev = &bcache.head;
  //   bcache.head.next->prev = b;
  //   bcache.head.next = b;
  // }
  
  release(&hash_locks[bucket]);
}

void
bpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt++;
  release(&bcache.lock);
}

void
bunpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt--;
  release(&bcache.lock);
}