Survey data structures inside the sv6 or scalefs

[kjhnet]

• Find suitable data structures to which RLU/MV-RLU can be applied in sv6 or scalefs.
• Data structures currently protected by RCU or spinlock might be a good candidate.
• RLU/MV-RLU can protect a shared data structure in scheduler, VM, filesystem, network stack.

[kjhnet]

• Related work
  • RadixVM: https://pdos.csail.mit.edu/archive/multicore/radixvm/
  • Scalable range lock: https://dl.acm.org/doi/pdf/10.1145/3342195.3387533
  • BRAVO - Biased locking for rwlocks: https://www.usenix.org/conference/atc19/presentation/dice
  • FastMap: https://www.usenix.org/conference/atc20/presentation/papagiannis

[kjhnet]

• 1st step

  • linked list, hash table 등의 자료구조가 lock (or RCU)에 의해 보호되는 영역(코드) 찾기
  • 해당 코드를 RLU/MV-RLU를 이용하여 동기화 함
  • 해당 코드에 부하를 줄 수 있는 벤치마크 실행

• 2nd step

  • 동기화가 필요한 아주 간단한 영역 찾기 (예: 레퍼런스 카운팅 관리)
  • 해당 영역을 RLU/MV-RLU를 이용하여 동기화 함
  • 해당 영역에 부하를 줄 수 있는 벤치마크 실행

• 3rd step

  • VMA(virtual memory area)를 관리하는 서버 시스템 동기화
  • Related work 논문 참고하여 RLU/MV-RLU로 병렬성 높일 수 있는 구조 설계
  • 해당 논문에서 사용한 벤치마크로(예: Metis) 부하 실험

• 4th step

  • 동기화로 인한 bottleneck 발생 모든 영역이 대상이 됨
  • RLU/MV-RLU로 동기화 구조 설계
  • 다양한 벤치마크 활용

[kjhnet]

• Candidates
  • include/snzi.hh : cookie inc( ) { }, void dec( ) { }, struct node { }
  • include/chainhash.hh: bool insert( ) { }, bool remove( ) { }
    • they are used in many places (e.g., filesystem)

[bigsys-gnu]

• RadixVM

  • RadixVM은 non-overlapping되는 VMA(virtual memory area)에 대하여 여러 스레드가 동시에 mmap, munmap, pagefault를 허용함

  • RadixVM을 구현하기 위해 radix-tree 자료구조를 사용하였으며 thread safety를 위해 lock acquire, release(include/radix_array.hh) 를 사용함.

  • radix-tree lock을 MV-RLU로 대체(또는 일부) 가능한지 고려

  • include/radix_array.hh

  • void lock( ) const: cref->get_lock().acquire(bit_spinlock::cli_caller) 에서 hand over hand 방식으로 spinlock을 이용해서 lock

  • 코드상으로는 lock을 잡는 부분에서 thread간 contention이 발생할 것으로 보이는데 Perf나 gdb등으로 확인 필요함

[bigsys-gnu]

• ScaleFS
  • kernel/scalefs.cc: chainhash로 다양한 자료구조 생성

[gitrvy2]

radix tree 간단 분석결과입니다.

• 현재 구현된 radix tree는 노드별로 스핀락을 할당합니다. 각 노드는 메모리 주소 하나에 대응합니다.
• vm에서 메모리 맵을 사용할 때는 주소 범위를 지정해서 lock을 획득 및 반환합니다. 이떄 범위내 각 메모리 주소 (노드)의 락을 순차적으로 처리합니다.
• 구조상으로는 각 노드의 스핀락(bit_spinlock.hh)을 mvrlu로 대체 할 수 있어보이는데 자세한건 해 봐야 알겠습니다..
• 어떤걸 벤치마크로 사용할 지는 아직 확인을 해봐야 하겠지만, vm에서 활용하는 메모리 영역이 겹치는 경우가 많이 있으면 어느정도 성능 비교는 가능해 보입니다.
• 그런데 RadixVM은 겹치지 않는 주소범위에서 scalability를 제공하는 연구기 때문에 과연 벤치마크가 성실하게 겹치는 케이스를 많이 발생하도록 했는지는 확인해 봐야합니다 (중요!)

다음은 refcache 관련 분석결과입니다.

• 일단 레퍼런스 카운팅을 하는 refcache는 radix tree와는 별개의 부분입니다. (RadixVM의 3가지 솔루션 중 하나)
• refcache(refcache.hh)도 spinlock를 사용하기 때문에 mvrlu로 대체가 가능한지 검토해 보겠습니다.

Radixtree의 마지막 솔루션인 TLB Shootdown은 저희가 건드릴 수 있는 영역이 아닌것 같습니다.

[bigsys-gnu]

radix tree 간단 분석결과입니다.

• 현재 구현된 radix tree는 노드별로 스핀락을 할당합니다. 각 노드는 메모리 주소 하나에 대응합니다.
• vm에서 메모리 맵을 사용할 때는 주소 범위를 지정해서 lock을 획득 및 반환합니다. 이떄 범위내 각 메모리 주소 (노드)의 락을 순차적으로 처리합니다.
• 구조상으로는 각 노드의 스핀락(bit_spinlock.hh)을 mvrlu로 대체 할 수 있어보이는데 자세한건 해 봐야 알겠습니다..
• 어떤걸 벤치마크로 사용할 지는 아직 확인을 해봐야 하겠지만, vm에서 활용하는 메모리 영역이 겹치는 경우가 많이 있으면 어느정도 성능 비교는 가능해 보입니다.
• 그런데 RadixVM은 겹치지 않는 주소범위에서 scalability를 제공하는 연구기 때문에 과연 벤치마크가 성실하게 겹치는 케이스를 많이 발생하도록 했는지는 확인해 봐야합니다 (중요!) ==> RadixVM 논문 사용한 벤치마크 또는 sv6/scalefs 내에 있는 벤치마크를 이용

다음은 refcache 관련 분석결과입니다.

• 일단 레퍼런스 카운팅을 하는 refcache는 radix tree와는 별개의 부분입니다. (RadixVM의 3가지 솔루션 중 하나)
• refcache(refcache.hh)도 spinlock를 사용하기 때문에 mvrlu로 대체가 가능한지 검토해 보겠습니다. ==> refcache에서 사용하는 spinlock을 mvrlu로 대체하는 부분이 좀더 간단하거나 성능 향상 폭이 클 수 있으니 살펴봅시다. ==> refcache를 평가할 수 있는 적절한 벤치마크 찾기 in scalefs/sv6

Radixtree의 마지막 솔루션인 TLB Shootdown은 저희가 건드릴 수 있는 영역이 아닌것 같습니다.