// 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"


// TODO: use sleeplock instead of spinlock

struct {
  struct spinlock lock;
  struct buf buf[NBUF];
  #define NHASH 233
  // struct hash_t{
  //   uint pos;
  //   struct hash_t *nxt;
  // }hash[NHASH];
  uint hash_head[NHASH];
  uint nxt[NBUF];
  struct spinlock hashlock[NHASH];
  uint freelist_head[NCPU];
  // 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;
  struct spinlock freelistlock[NCPU];
} bcache;

uint hasher(uint dev,uint blockno){
  return ((uint64)dev<<32|blockno)%NHASH;
}

int hash_get(uint dev,uint blockno){
  const uint hash_pos=hasher(dev, blockno);
  int pos=-1;
  // acquire(&bcache.hashlock[hash_pos]);
  for(int cur=bcache.hash_head[hash_pos];cur!=-1;cur=bcache.nxt[cur])
    if(bcache.buf[cur].dev==dev && bcache.buf[cur].blockno==blockno){
      pos=cur;
      goto RET;
    }
  
  RET:

  // release(&bcache.hashlock[hash_pos]);
  // printf("%u\n",pos);
  return pos;
}

void hash_add(uint dev,uint blockno,uint buf_pos){
  const uint hash_pos=hasher(dev, blockno);
  // acquire(&bcache.hashlock[hash_pos]);
  bcache.nxt[buf_pos]=bcache.hash_head[hash_pos];
  bcache.hash_head[hash_pos]=buf_pos;
  // release(&bcache.hashlock[hash_pos]);
}

void hash_del(uint dev,uint blockno){
  const uint hash_pos=hasher(dev, blockno);
  push_off();
  const uint cpu=cpuid();
  pop_off();
  acquire(&bcache.hashlock[hash_pos]);
  for(int cur=bcache.hash_head[hash_pos],pre=-2;cur!=-1;cur=bcache.nxt[cur]){
      if(bcache.buf[cur].dev==dev && bcache.buf[cur].blockno==blockno){
        struct buf *b=&bcache.buf[cur];
        --b->refcnt;
        if (b->refcnt == 0) {
          if(pre==-2){// the head is what we are looking for
            bcache.hash_head[hash_pos]=bcache.nxt[cur];
          }else{
            bcache.nxt[pre]=bcache.nxt[cur];
          }
          bcache.nxt[cur]=-1;
          for(int i=cpu;;i=(i+1)%NCPU){
            push_off();
            if(holding(&bcache.freelistlock[i])){
              pop_off();
              continue;
            }
            pop_off();
            acquire(&bcache.freelistlock[i]);
            const int pos=b-bcache.buf;
            // printf("%d\n",pos);
            bcache.nxt[pos]=bcache.freelist_head[i];
            bcache.freelist_head[i]=pos;

            // DEBUG();
            // printf("%u\n",bcache.freelist_head);

            release(&bcache.freelistlock[i]);
            break;
          }
          break;
        }
      }
      pre=cur;
  }
  release(&bcache.hashlock[hash_pos]);
}

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");
  for(int i=0;i<NHASH;i++){
    initlock(&bcache.hashlock[i], "bcache_hashtable");
    bcache.hash_head[i]=-1;
  }
  for(int i=0;i<NCPU;++i){
    bcache.freelist_head[i]=-1;
    initlock(&bcache.freelistlock[i], "bcache_freelist");
  }
  // Create linked list of buffers
  // bcache.head.prev = &bcache.head;
  // bcache.head.next = &bcache.head;
  int which=0;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    // b->next = bcache.head.next;
    // b->prev = &bcache.head;
    initsleeplock(&b->lock, "buffer");
    const uint cur=b-bcache.buf;
    bcache.nxt[cur]=bcache.freelist_head[which];
    bcache.freelist_head[which]=cur;
    which=(which+1)%NCPU;
    // 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;
  // acquire(&bcache.lock);
    const uint hash_pos=hasher(dev, blockno);
  acquire(&bcache.hashlock[hash_pos]);
  const int pos=hash_get(dev, blockno);
  // Is the block already cached?
  // for(b = bcache.head.next; b != &bcache.head; b = b->next){
  //   if(b->dev == dev && b->blockno == blockno){
  //     b->refcnt++;
  //     release(&bcache.lock);
  //     acquiresleep(&b->lock);
  //     return b;
  //   }
  // }
  if(pos>=0){
    b=&bcache.buf[pos];
    // acquire(&bcache.hashlock[hash_pos]);
    ++bcache.buf[pos].refcnt;
    release(&bcache.hashlock[hash_pos]);
    acquiresleep(&b->lock);
    // release(&bcache.lock);
    return b;
  }
  push_off();
  const uint cpu=cpuid();
  pop_off();
  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  for(int i=cpu;;i=(i+1)%NCPU){
    push_off();
    if(holding(&bcache.freelistlock[i])){
      pop_off();
      continue;
    }
    pop_off();
    acquire(&bcache.freelistlock[i]);
    if(bcache.freelist_head[i]==-1){
        release(&bcache.freelistlock[i]);
        continue;
    }
    // DEBUG();
    // for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    //   if(b->refcnt == 0) {
    //     hash_add(dev, blockno, b-bcache.buf);
    //     b->dev = dev;
    //     b->blockno = blockno;
    //     b->valid = 0;
    //     b->refcnt = 1;
    //     release(&bcache.lock);
    //     acquiresleep(&b->lock);
    //     return b;
    //   }
    // }
    // for(uint cur=bcache.freelist_head;cur!=-1;cur=bcache.nxt[cur])
    // DEBUG();
    // printf("%u\n",bcache.freelist_head);
    b=&bcache.buf[bcache.freelist_head[i]];
    const int ori=bcache.freelist_head[i];
    bcache.freelist_head[i]=bcache.nxt[bcache.freelist_head[i]];
    hash_add(dev,blockno,ori);
    release(&bcache.hashlock[hash_pos]);    
    b->dev=dev;
    b->blockno=blockno;
    b->valid=0;
    b->refcnt=1;
    release(&bcache.freelistlock[i]);
    acquiresleep(&b->lock);
    // release(&bcache.lock);
    return b;
  }
  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);

  // acquire(&bcache.lock);
  
  hash_del(b->dev, b->blockno);
    // 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;gi

  
  
  // release(&bcache.lock);
}

void
bpin(struct buf *b) {
  // acquire(&bcache.lock);
  const uint hash_pos=hasher(b->dev, b->blockno);
  acquire(&bcache.hashlock[hash_pos]);
  b->refcnt++;
  release(&bcache.hashlock[hash_pos]);
  // release(&bcache.lock);
}

void
bunpin(struct buf *b) {
  // acquire(&bcache.lock);
  const uint hash_pos=hasher(b->dev, b->blockno);
  acquire(&bcache.hashlock[hash_pos]);
  b->refcnt--;
  release(&bcache.hashlock[hash_pos]);
  // release(&bcache.lock);
}