Posix Eşzamanlılık Yapıları - Spinlock

Giriş
Bu yapıyı user space içinde kullanmak iyi bir fikir olmayabilir. Açıklaması şöyle.

Spinlocks are often considered a wrong tool in user-space because there is no way to disable thread preemption while the spinlock is held (unlike in kernel).

So that a thread can acquire a spinlock and then get preempted, causing all other threads trying to acquire the spinlock to spin unnecessarily (and if those threads are of higher priority that may cause a deadlock (threads waiting for I/O may get a priority boost on wake up)).

This reasoning also applies to all lockless data structures, unless the data structure is truly wait-free (there aren't many practically useful ones, apart from boost::spsc_queue).

Kernel (çekilrdekte) durum farklı. Açıklaması şöyle.

In kernel, a thread that has locked a spinlock cannot be preempted or interrupted before it releases the spinlock. And that is why spinlocks are appropriate there

Linux'ta SpinLock için Iteration Sayabilen Bir Yapı Var
Açıklaması şöyle.

On Linux, there is adaptive mutex PTHREAD_MUTEX_ADAPTIVE_NP, which spins for a limited number of iterations before blocking in the kernel (similar to InitializeCriticalSectionAndSpinCount). However, that mutex cannot be used through std::mutex interface because there is no option to customise non-portable pthread_mutexattr_t before initialising pthread_mutex_t.

One can neither enable process-sharing, robustness, error-checking or priority-inversion prevention through std::mutex interface. In practice, people write their own wrappers of pthread_mutex_t which allows to set desirable mutex attributes; along with a corresponding wrapper for condition variables. Standard locks like std::unique_lock and std::lock_guard can be reused.

Posix Eşzamanlılık Yapıları - Semaphore

Semaphore
Genel kullanım amacı bir kaynağa aynı anda kaç kişini erişebileceğini kontrol etmektir. Şu dosyayı include etmek gerekir.

#include <semaphore.h>

Posix ile iki çeşit semaphore kullanılabilmekte. İlki named semaphore, diğeri ise unnamed semaphore. Burada dikkat edilmesi gereken nokta unnamed semaphore uygulamalar arasından paylaşılamaz anlamına gelmiyor.

1. Named Semaphore
Bu semaphore hep bir pointer olarak tutuluyor.

sem_t *mySemaphore;

Named semaphore yapısına bir isim verilerek erişiliyor. ARINC 653 veya OS X gibi bazı işletim sistemleri sadece Named Semaphore kullanımını destekliyorlar.

POSIX standardında Named semaphore ile sem_open(),sem_close() ve sem_unlink() metodları kullanılıyor.

sem_open metodu
Bu yapıyı oluşturmak için sem_open metodu kullanılıyor. O_CREAT flag'i ile kullanılırsa, named semaphore yaratılmamışsa yaratılır.

const char* name = "/permission_test_semaphore";
sem_t* sem = sem_open(name, O_CREAT | O_EXCL, 0644, 0);
if (SEM_FAILED == sem){...}

Bir başka örnek

const char *semaphore_name = "my-test-semaphore";

int rc = sem_unlink(semaphore_name);
if (rc)
  perror("sem_unlink");

sem_t *semaphore = sem_open(semaphore_name, O_CREAT, O_RDWR, 0);
if (semaphore == SEM_FAILED) {
  perror("sem_open");
  return 1;
}

rc = sem_wait(semaphore);
if (rc) {
  perror("sem_wait");
  return 1;
}

sem_close metodu
Örnek vermem lazım.

sem_unlink metodu
sem_open ile açılan bir yapı sem_unlink ile kaldırılır.

sem_open ile kullanılan dosya ismi
Buradaki soruda açıklandığı gibi  sem_open ile verilen dosya ismi sistemde tekil olmalı. POSIX standardı isimin şeklini ve uzunluğunu açık bırakmış. Ancak soruda da açıklandığı gibi en portable isimler "/semaphore_tekil_ismi" şeklinde olanlar.

dosya sistemi
Bu semaphore türü dosya sistemini kullanıyor. Örneğin Linux'ta /dev/shm dizinine, Solaris'te ise /tmp dizinine erişim hakkı olmalı.

2. Unnamed Semaphore
İsimsiz semaphore yapısı için sem_init(), sem_destroy() metodları kullanılıyor. Bu konu ile ilgili sem_overview başlıklı yazı biraz daha açıklama sunuyor.

sem_init metodu
Metodun imzası şöyle

int sem_init(sem_t *sem, int pshared, unsigned int value); 

Açıklaması şöyle.

• sem points to a semaphore object to initialize
• pshared is a flag indicating whether or not the semaphore should be shared with fork()ed processes. LinuxThreads does not currently support shared semaphores
• value is an initial value to set the semaphore to

Value değeri kullanıma hazır kaç tane kaynak olduğunu gösterir. Örneğin kuyrukta işlemeye hazır bir nesne varsa bu değer 1 ile başlatılır.
Örnek
Şöyle yaparız.

 sem_init(&finish, 0, 0);

a. fork ile kullanılan sem_init
Semaphore hep bir pointer olarak tutuluyor.

sem_t *mySemaphore

sem_init() metoduna geçilen pshared parametresi, bu isimsiz semaphore nesnesinin uygulamalar arasında paylaşılıp paylaşılamayacağını gösteriyor.
Paylaşılan bir semaphore şöyle açılır. Bu örnek fork yapan uygulamalar için uygundur.

sem_t* semp = (sem_t*)mmap(0, sizeof(sem_t),PROT_READ|PROT_WRITE,
                           MAP_ANONYMOUS|MAP_SHARED,0,0);
if ((void*)semp == MAP_FAILED) { perror("mmap");  exit(EX_OSERR); } 

sem_init(semp, 1 /*shared*/, 0 /*value*/);

b. Thread'ler Arası kullanılan sem_init
Bu semaphore pointer olarak tutulmak zorunda değil çünkü mmap yapmak gerekmez. Bu yüzden ikinci parametre 0 geçilir. Aşağıdaki örnekte kullanıma hazır 1 kaynak ile başlanıyor.

sem_t sem;
sem_init(&sem, 0, 1);

Kullanacak hiç kaynak yoksa şöyle yaparız.

sem_init(&sem, 0, 0);

3. Tüm Semaphore'lar İçin Metodlar
Named veya Unnamed tüm semaphore ile kullanılabilecek metodlar ise aşağıda

Semaphore ile ilgili bazı notlar şunlar:
sem_t değişkeni başka bir değişkene kopyalanamaz.

semp_post metodu
Şöyle yaparız. Semaphore nesnesinin değerini 1 artırır. Örneğin kuyruğa işlemek için yeni bir nesne eklenince bu metodu çağırırız.

sem_post(&sem);

sem_wait metodu
Şöyle yaparız. Örneğin kuyrukta işlemek için yeni bir nesne var mı kontrolünü yapmak için bu metodu çağırırız.

sem_wait(&sem);

semaphore'un değeri sıfır ise çağıran thread'i bloke eder.Ancak burada dikkat edilmesi gereken nokta, sem_wait EINTR ile bölünebilir. Bu durumda metodun döndürdüğü değere ve hata koduna bakmak lazım. Örnek:

/* Just wait for the semaphore */
do {
  result = (0 == sem_wait(&self->semaphore));
  if (!result) {
    result = errno;
  }
} while (EINTR == result);

Benim asıl ilgincime giden Qt ile gelen QSemaphore sınıfının her iki metodu da kullanmaması. Bu sınıf kaynak kodundan da görüldüğü gibi semaphore işlevini yerine getirmek için basit bir mutex ve sayaç kullanıyor.

sem_trywait
semaphore'un değeri sıfır ise -1 döner ve errno değişkeninin değerini EAGAIN olarak atar.

sem_destroy metodu
semaphore üzerinde bekleyen thread varsa, bu işlemin sonucu tanımsızdır (undefined ). Şöyle yaparız

sem_destroy(&sem);

sem_getvalue
semaphore'un değerini döndürür. Bu metod ile belirtilen semaphore üzerinde bloke olmuş kaç thread var öğrenilebilir. Anladığım kadarıyla POSIX bu metodun ya 0 ya da eksi bir sayı dönmesine izin veriyor. 0 dönerse işletim sistemi bu çağrıyı desteklemiyor anlamına geliyor. Eksi bir sayı dönerse mutlak değeri alınarak kullanılmalı ve bloke olan thread sayısını belirtiyor. Ancak bu çağrı sadece bir anlık görüntü (snapshot) döndürdüğü için pratikte ne işe yarar ben de anlamadım.

Bir semaphore mutex'in yerini alabilir mi ?

Alamaz

1. Semaphore'un üst sınırı vardır. Mutex recursive ise n-defa da aynı kişi tarafından lock edilse çalışır ancak semaphore'un üst sınırı vardır vardır ve sadece sınırlı kez lock edilebilir. Yani kişi kendi kendini dead-lock haline sokabilir.
2. Counting Semaphores, Binary Semaphores and Mutexes explained başlıklı yazıdan da görülebileceği gibi semaphore'un sahibi yoktur. Semaphore lock etmiş herhangi bir thread tarafından da unlock edilebilir. Mutex ise sadece lock etmiş thread tarafından unlock edilebilir.

Ayrıca Producer/Consumer kuyruklarında semaphore Producer şöyle kodlanır. Yani her zaman mutex kullanılır.

while (1) {
  pthread_mutex_lock(&mutex);  InsertAtHead(...);
  pthread_mutex_unlock(&mutex);

  sem_post(&semaphore);
 
}

Consumer şöyle kodlanır.

while (1) {
  sem_wait(&semaphore);
  
  pthread_mutex_lock(&mutex);
  PopTail();
  pthread_mutex_unlock(&mutex);
  
}

Bir binary semaphore mutex'e nerede tercih edilmeli ?
Where to use binary semaphore when mutex are available? yazısında da anlatıldığı gibi binary semaphore iki uygulama arasında bekle/devam et (wait/notify) tarzı iletişim için kullanılıyorsa mutex'ten daha kullanışlı.

Semaphore ve Bekleme Listesi
wait queues vs semaphores in linux başlıklı soruda Linux üzerinde de aynı mutex'te olduğu gibi bir bekleme listesi olduğu yazılı.

Kernel ve Stack

Not : Bu yazı ile ilgili olarak Segmentation Fault başlıklı yazıya göz atabilirsiniz.


Stack Boyutu
Linux üzerinde stack boyutunu ayarlamak mümkün. Buradaki şekilde durum görülebilmektedir.

Address space layout randomization
Bu yöntemde stack'in başlangıç adresi, kullandığı guard page sayısı rastgele seçilerek, buffer overflow saldırılarına karşı tedbir alınıyor.

Stack'in Yönü
Çoğu mimaride stack aşağıya doğru büyür. Bunu görmek için şöyle yaparız.

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

static ptrdiff_t
stack_probe(uintptr_t stack_addr_from_main)
{
  int var;
  uintptr_t stack_addr_from_me = (uintptr_t)&var;

  return ((intptr_t) stack_addr_from_me) - 
         ((intptr_t) stack_addr_from_main);
}

int main(void)
{
  int var;
  uintptr_t stack_addr_from_main = (uintptr_t)&var;
  ptrdiff_t stack_delta = stack_probe(stack_addr_from_main);
  printf("Stack offset from one function call = %td\n", stack_delta);
  return 0;
}

Linux ve ulimit komutu
Linux üzerinde stack boyutunu ayarlamak için ulimit komutu kullanılabilir.

Windows ve Enhanced Mitigation Experience Toolkit

Buradaki soruda, EMET aracı kullanılarak, kaç tane stack guard sayfasının konulabileceği ayarlanmış.

Stack Clash
Açıklaması şöyle

Stack Clash is an exploit based on a fairly old technique. The memory used by a process is divided into two regions - the stack and the heap. One generally imagines the stack as growing downwards and the heap as growing upwards. What happens when the either grows enough to clash with the other? More generally, what happens when the stack grows enough to encroach into unrelated memory spaces? The original vulnerability is 12 years old, and the Linux kernel developers fixed it temporarily by using a guard page. However, researchers at Qualys have managed to exploit this despite the guard page.

Stackoverflow Olursa - C#
C#'ta stackoverflow olursa, JIT için kod derleyecek yeterli yer kalmadığı için kurtulmak mümkün değil.

Stackoverflow Olursa -Java
Java JIT kullanmak zorunda olmadığı için stackoverflow'dan kurtulabilir. Örnek:

public class Test
{
    public static void main(String[] args)
    {
        try {
            foo();
        } catch (StackOverflowError e) {
            bar();
        }
        System.out.println("normal termination");
    }

    private static void foo() {
        System.out.println("foo");
        foo();
    }

    private static void bar() {
        System.out.println("bar");
    }
}

C++ Windows
Stack'te yaratılan değişkenlerde buffer overflow olursa yakalanabilir.
Proje / C7C++ / Code Generation / Basic Runtime Cheks = Both yapılır.  Aşağıdaki örnek çalıştırılırsa stack hatası yakalanır.

int main (int argc, char* argv[]){
 char buf [1];
 buf [1] = 'A';
 return 1;
}

Programdan çıkarken Run-Time Check Failure #2 - Stack around the variable 'buf' was corrupted pop-up mesajı gelir.

Stack ve API
Aşağıda stack bilgisini alma ve atamayla ilgili bazı API açıklamaları var.

Windows 8
Stack boyutunu öğrenmek mümkün.

ULONG_PTR lowLimit;
ULONG_PTR highLimit;
GetCurrentThreadStackLimits(&lowLimit, &highLimit);

Posix pthread_getattr_np metodu

pthread_getattr_np ve pthread_attr_getstack metodlarını kullanarak bir threadin kullandığı stack boyunu öğrenmek mümkün.

Posix pthread_attr_setstack metodu
pthread_attr_setstack metodu ile bir threadin kullandığı stack boyutunu atamak mümkün.
pthread_attr_getstack metodu ile bir threadin kullandığı stack boyutunu öğrenmek mümkün.

Stack boyutunu atamak için kullanılacak stack'i kullanıcının yaratması gerekiyor.

Posix pthread_attr_setguardsize metodu
Bazı derleyiciler Buffer Overflow hatalarını yakalamak için Heap ve Stack segmentleri arasına "Guard Page" denilen veri yapıları yerleştirirler. Böylece stack bölümündeki bir taşmayı yakalamak mümkün olur.

pthread_attr_setguardsize metodu ile stack için guard alanı yaratmak mümkün.
How to set stack_size, stack_addr and guardsize when creating a thread başlıklı soruda bu konu daha iyi açıklanmış. Bu konu ile ilgili olarak Segmentation Fault başlıklı yazıya göz atabilirsiniz.

Compiler her zaman Stack Kullanmak Zorunda Değildir
Bir metod çağırıldığı zaman eski metod içindeki her şey stack'e atılır ve yeni metod'a geçilen parametreler de dahil olmak üzere yeni bir stack yaratılır diye biliyordum ancak c & gcc : Stack growth and alignment - for a 64 bit machine sorunda da görülebildiği gibi compiler yeni çağırılan metoda geçilen parametreleri ESI ve EDI register'larına yazarak stack kullanmadan bir metod da çağırabiliyormuş.What is exactly the base pointer and stack pointer? To what do they point? sorusuna verilen cevaplardan birisi olan şu cümle ile ne kast ettiğim daha iyi anlaşılabilir.

Generally (and this may vary from compiler to compiler), all of the arguments to a function being called are pushed onto the stack (usually in the reverse order that they're declared in the function prototype, but this varies).