6. Radix Tree추가해보기 2부 (실제 코딩)

ㅇ1. nova_sb_info에 Radix Tree root를 선언한다.

<super.h> struct nova_sb_info에 추가

2. dedup_test에서 SB 뽑아서 radix_tree 초기화해보기

그동안 판 시스템 콜들이 제대로 작동하는지를 알기 위해 경로에 printk들을 심어두었다. 

// dedup/dedup.c

#include<linux/kernel.h>
#include<linux/syscalls.h>
#include<linux/file.h>
#include<linux/fs.h>

int real_dedup(struct file *file){
  printk("System Call level\n");
  if(file->f_op->dedup){
    printk("calling dedup\n");
    return file->f_op->dedup(file);
  }
  return 0;
}

int ksys_dedup(unsigned int fd){
  struct fd f = fdget_pos(fd);
  if(f.file){
    return real_dedup(f.file);
  }
  return 0;
}


SYSCALL_DEFINE1(dedup, unsigned int, fd){
  return ksys_dedup(fd);
}

// fs/nova/file.c

static int nova_dedup(struct file *filp){
  printk("hi\n");
  if(filp->f_op->dedup)
    printk("dedup exists\n");
  struct address_space *mapping = filp->f_mapping;
  struct inode *inode = mapping->host;

  printk("Dedup Function Called\n");

  sb_start_write(inode->i_sb);
  inode_lock(inode);
  printk("Calling dedup_test\n");
  dedup_test(filp);
  inode_unlock(inode);
  sb_end_write(inode->i_sb);

  return 1;
}

// fs/nova/dedup.c

#include <linux/slab.h>
#include <linux/uio.h>
#include <linux/uaccess.h>
#include <linux/falloc.h>
#include <asm/mman.h>

#include "nova.h"
#include "inode.h"
#include "dedup.h"



int dedup_test(struct file * filp){
  struct address_space *mapping = filp->f_mapping;  
  struct inode *inode = mapping->host;
  struct super_block *sb = inode->i_sb;
  struct nova_sb_info *sbi = NOVA_SB(sb);

  INIT_RADIX_TREE(&sbi->dedup_tree_fingerprint,GFP_KERNEL);

  printk("Radix Tree Initialized\n");

  return 0;
}

결과:

순차적으로 호출이 잘되는 것을 확인할 수 있다.

 

3. Radix Tree 삽입 + 탐색해보기.

dedup.c에서 Super block에 저장된 Radix tree를 읽어와 봤다. 이제 Radix Tree에 값을 넣고 읽어오는 것이 가능한지 실험해본다. 사용한 함수는 radix_tree_insert, radix_tree_lookup, radix_tree_deref_slot이다. 다른 건 직관적인데 deref는 무엇일까? 이는 linux 공부 section에도 있지만, lookup이 반환하는 것은 slot에 대한 pointer이다. radix_tree_deref_slot을 통해서만 해당 slot에 저장된 내용, 구조체, 를 확인할 수 있는 것이다.

// include/linux/radix-tree.h

/** 
 * radix_tree_deref_slot	- dereference a slot
 * @pslot:	pointer to slot, returned by radix_tree_lookup_slot
 * Returns:	item that was stored in that slot with any direct pointer flag
 *		removed.
 *
 * For use with radix_tree_lookup_slot().  Caller must hold tree at least read
 * locked across slot lookup and dereference. Not required if write lock is
 * held (ie. items cannot be concurrently inserted).
 *
 * radix_tree_deref_retry must be used to confirm validity of the pointer if
 * only the read lock is held.
 */
static inline void *radix_tree_deref_slot(void **pslot)
{
	return rcu_dereference(*pslot);
}

아래가 최종적으로 작성한 코드이다.

// fs/nova/dedup.c

#include <linux/slab.h>
#include <linux/uio.h>
#include <linux/uaccess.h>
#include <linux/falloc.h>
#include <asm/mman.h>

#include "nova.h"
#include "inode.h"
#include "dedup.h"

struct dedup_node{
  long long dedup_table_entry;
};


void nova_init_dedup_entry(struct dedup_node * entry){
  memset(entry,0,sizeof(struct dedup_node));
  entry->dedup_table_entry = 1;
}


int dedup_test(struct file * filp){
  struct dedup_node temp;
  void ** temp2; 
  struct dedup_node *temp3;

  struct address_space *mapping = filp->f_mapping;  
  struct inode *inode = mapping->host;
  struct super_block *sb = inode->i_sb;
  struct nova_sb_info *sbi = NOVA_SB(sb);

  printk("fs/nova/dedup.c\n");

  INIT_RADIX_TREE(&sbi->dedup_tree_fingerprint,GFP_KERNEL); 
  printk("Radix Tree Initialized\n");

  nova_init_dedup_entry(&temp);

  radix_tree_insert(&sbi->dedup_tree_fingerprint,32,&temp); 
  printk("Inserted!\n");
  temp2 = radix_tree_lookup_slot(&sbi->dedup_tree_fingerprint,32);

  if(temp2){
    printk("Found Entry\n");
    temp3 = radix_tree_deref_slot(temp2);
    printk("%lld\n",temp3->dedup_table_entry);
  }

  return 0;
}

1을 찾는 모습

 

4. 앞으로 할 일

- dedup_node entry안에 들어갈 자료들 정하기

- dedup table을 저장할 파일 만들거나 형식 생각하기

- write entry에 dedup_flag설정해보기

- 등등