wiki:kernel_locks

Version 16 (modified by alain, 9 years ago) (diff)

--

GIET-VM / Locks access functions

The kernel_locks.c and kernel_locks.h files define the functions used by the kernel to take & release locks protecting exclusive access to shared resources.

The GIET_VM kernel define three types of locks:

  1. The simple_lock_t implements a non-distributed spin-lock without waiting queue.
  1. The spin_lock_t implements a spin-lock with a waiting queue (based on a ticket allocator scheme), to enforce fairness and avoid live-lock situations.
  1. The sqt_lock_t spin-lock can be used when a single lock protect a unique resource shared by a large number of tasks running on a 2D mesh clusterised architecture. The lock is implemented as a Synchronisation Quad Tree (SQT) of partial spin_locks distributed on all cluster, and is intended to avoid contention on a single cluster when all tasks try to access the same resource.

All the lock access functions are prefixed by "_" to remind that they can only be executed by a processor in kernel mode.

The simple_lock_t, sbt_lock_t, and spin_lock_t structures are implemented to have one single lock in a 64 bytes cache line, and should be aligned on a cache line boundary.

Atomic access function

unsigned int _atomic_increment( unsigned int * shared , unsigned int increment )

This blocking function uses LL/SC to atomically increment a shared variable.

  • shared : pointer on the shared variable
  • increment : increment value

It returns the value of the shared variable before increment.

void _atomic_or( unsigned int *shared , unsigned int mask )

This blocking function uses LL/SC to atomically set a bit field in a shared variable.

  • shared : pointer on the shared variable.
  • mask : *ptr <= *ptr | mask

void _atomic_and( unsigned int *shared , unsigned int mask )

This blocking function uses LL/SC to atomically reset a bit field in a shared variable.

  • shared : pointer on the shared variable.
  • mask : *ptr <= *ptr & mask

Simple lock access functions

void _simple_lock_acquire( simple_lock_t * lock )

This blocking function does not implement any ordered allocation, and is not distributed. It returns only when the lock as been granted.

void _simple_lock_release( simple_lock_t * lock )

This function releases the lock, and can be used for lock initialisation. It must always be called after a successful _simple_lock_acquire().

Queuing Lock Access functions

void _spin_lock_init( spin_lock_t * lock )

This function initializes the spin_lock ticket allocator.

void _spin_lock_acquire( spin_lock_t * lock )

This blocking function uses the atomic_increment() function, to implement a ticket allocator and provide ordered access to the lock. It returns only when the lock as been granted.

void _spin_lock_release( spin_lock_t * lock )

This function releases the lock, but cannot be used for lock initialisation. It must always be called after a successful _lock_acquire().

Distributed Lock Access functions

void _sqt_lock_init( sqt_lock_t* lock )

This function allocates and initialises the SQT nodes, distributed on all clusters. It computes the smallest SQT covering all processors defined in the mapping. This function use the _remote_malloc() function, and the distributed kernel heap segments.

void _sqt_lock_acquire( sqt_lock_t* lock )

This function tries to acquire the SQT lock: It tries to get each "partial" lock on the path from bottom to top, using an atomic LL/SC, and starting from bottom. It is blocking : it polls each "partial" lock until it can be taken, and returns only when all "partial" locks, at all levels have been obtained.

void _sqt_lock_release( sqt_lock_t* lock )

This function releases the SQT lock: It reset all "partial" locks on the path from bottom to top, using a normal write, and starting from bottom.