Implementacja CLH-lock w Asemblerze x86-64

static queuelock_t lock;
static unsigned long int counter = 0;

static int test(void)
{
    int i;
    long int id;
    for (i = 0; i < 10000000; ++i) {
        id = queuelock_lock(&lock);
        ++counter;
        queuelock_unlock(&lock, id);
    }
}

malloc(): unaligned tcache chunk detected
malloc(): unaligned tcache chunk detected
Przerwane (zrzut pamięci)

free(): unaligned chunk detected in tcache 2
Przerwane (zrzut pamięci)

free(): double free detected in tcache 2
free(): unaligned chunk detected in tcache 2
malloc(): unaligned tcache chunk detected
Przerwane (zrzut pamięci)

malloc(): unaligned tcache chunk detected
Przerwane (zrzut pamięci)

.intel_syntax noprefix

.globl queuelock_init
.globl queuelock_lock
.globl queuelock_unlock
.globl queuelock_destroy

.section .text,"ax",@progbits

queuelock_init:
xor     eax, eax
mov     QWORD PTR [rdi], rax
ret

queuelock_destroy:
or      rax, -1
test    QWORD PTR [rdi], rax
jne     0f
xor     eax, eax
0:
ret

queuelock_lock:
# node = malloc(...)
push    rdi
mov     edi, 8
call    malloc@PLT
pop     rdi

# node->locked = 1
mov     DWORD PTR [rax], 1

# pred = atomic_exchange(&tail, node)
push    rax
xchg    QWORD PTR [rdi], rax

# if (pred != NULL)
test    rax, rax
je      1f

# while (pred->locked) spin
0:
pause
test    QWORD PTR [rax], -1
jne     0b

# free(pred)
mov     rdi, rax
call    free@PLT

# return node
1:
pop     rax
ret

queuelock_unlock:
# if (CAS(&tail, node, NULL))
mov     rax, rsi
xor     edx, edx
lock cmpxchg QWORD PTR [rdi], rdx
jne     0f

# free(node)
mov     rdi, rsi
call    free@PLT

# return
xor     eax, eax
ret

# node->locked = 0
0:
xor     eax, eax
mov     QWORD PTR [rsi], rax

# return
ret

or      rax, -1
test    QWORD PTR [rdi], rax
jne     0f
xor     eax, eax
0:
ret

# node = malloc(...)
push    rdi
mov     edi, 8
call    malloc@PLT
pop     rdi

# while (pred->locked) spin
0:
pause
test    QWORD PTR [rax], -1
jne     0b

0:
xor     eax, eax
mov     QWORD PTR [rsi], rax

cmp QWORD PTR [rdi], 0
jne 0f

test QWORD PTR [rdi], -1
jne 0f

.intel_syntax noprefix

.globl queuelock_init
.globl queuelock_lock
.globl queuelock_unlock
.globl queuelock_destroy

.section .text,"ax",@progbits

queuelock_init:
xor     eax, eax
mov     QWORD PTR [rdi], rax
ret

queuelock_destroy:
test    QWORD PTR [rdi], -1
jne     0f
xor     eax, eax
ret
0:
or      eax, -1
ret

queuelock_lock:
push    rbp
mov     rbp, rsp
sub     rsp, 8

# node = malloc(...)
push    rdi
mov     edi, 8
call    fake_malloc
pop     rdi

# node->locked = 1
mov     DWORD PTR [rax], 1

# pred = atomic_exchange(&tail, node)
push    rax
xchg    QWORD PTR [rdi], rax

# if (pred != NULL)
test    rax, rax
je      1f

# while (pred->locked) spin
0:
pause
test    QWORD PTR [rax], -1
jne     0b

# free(pred)
mov     rdi, rax
call    fake_free

# return node
1:
pop     rax
leave
ret

queuelock_unlock:
push    rbp
mov     rbp, rsp

# if (CAS(&tail, node, NULL))
mov     rax, rsi
xor     edx, edx
lock cmpxchg QWORD PTR [rdi], rdx
jne     0f

# free(node)
mov     rdi, rsi
call    fake_free

# return
xor     eax, eax
leave
ret

# node->locked = 0
0:
xor     eax, eax
mov     QWORD PTR [rsi], rax

# return
leave
ret

#pragma once

int thread_create(int(*)(void*), void*);
void thread_exit(int) __attribute__ ((noreturn));

.intel_syntax noprefix

.globl thread_create
.globl thread_exit

.section .text,"ax",@progbits
thread_create:
push    rbp
mov     rbp, rsp

push    rdi
push    rsi

xor     edi, edi               # pid      = NULL
mov     eax, 302               # syscall  = prlimit64
xor     edx, edx               # new_rlim = NULL
lea     esi, DWORD PTR [rdi+3] # resource = RLIMIT_STACK
sub     rsp, 16
mov     r10, rsp               # old_rlim = ?
syscall                        # prlimit64(0, RLIMIT_STACK, NULL, rsp)

mov     edx, esi               # prot    = PROT_READ | PROT_WRITE
pop     rsi                    # length  = old_rlim.rlim_cur
add     rsp, 8
# xor   edi, edi               # addr    = NULL
mov     r10d, 0x4020022        # flags   = MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK | MAP_UNINITIALIZED
lea     eax, DWORD PTR [edi+9] # syscall = mmap
or      r8, -1                 # fd      = -1
mov     r9d, edi               # offset  = 0
syscall                        # mmap(NULL, old_rlim.rlim_cur, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK | MAP_UNINITIALIZED, -1, 0)

mov     rdx, rax               # arg3    = ?

lea     rdi, [rax+rsi-16]
pop     rax
stos    QWORD PTR es:[rdi], rax
pop     rax
stos    QWORD PTR es:[rdi], rax

mov     r10, rsi               # arg4    = old_rlim.rlim_cur
mov     edi, 0x53564d41        # arg2    = PR_SET_VMA
mov     rax, 0x6B63617473      # "stack"
xor     esi, esi               # option  = PR_SET_VMA_ANON_NAME
push    rax
mov     r8, rsp                # arg5    = "stack"
mov     eax, 157               # syscall = prctl
syscall                        # prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ?, limit.rlim_cur, "stack")

add     rsp, 8
lea     eax, [rsi+56]          # syscall = clone
mov     edi, 0x50F00           # flags   = CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | CLONE_SYSVSEM
lea     rsi, [rdx+r10]         # stack   = ?
syscall                        # clone(?, CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | CLONE_SYSVSEM)

test    rax, rax
jne     0f

sub     rsp, 16
pop     rdi
pop     rdx
xor     ebp, ebp
lea     rax, DWORD PTR [rip+1f]
push    rbp
push    rbp
mov     rbp, rsp
push    rax
jmp     rdx

0:
leave
ret

thread_exit:
xor     eax, eax
mov     al, 60                 # syscall = exit
syscall                        # exit(?)
1:
mov     rdi, rax               # status  = ?
jmp     thread_exit

#include <unistd.h>
#include <stdio.h>

#include "thread.h"
#include "queuelock.h"

#define MAX_THREADS 16

queuelock_t lock;
unsigned long int counter = 0;

unsigned int finished = 0; /* FIXME: unprotected in C, Assembly uses LOCK prefix */

extern int f(void*);

int main()
{
    int i;
    setvbuf(stdout, NULL, _IONBF, 0);
    queuelock_init(&lock);
    for (i = 1; i <= MAX_THREADS; ++i) {
        thread_create(f, NULL);
    }
    while (finished != MAX_THREADS) {
        sleep(1);
    }
    printf("%ld\n", counter);
    queuelock_destroy(&lock);
    return 0;
}

.intel_syntax noprefix

.globl f
.globl fake_malloc
.globl fake_free

.section .text,"ax",@progbits
0: .asciz "Thread %u Allocates\n"
1: .asciz "Thread %u Allocated %X\n"
fake_malloc:
push    rbp
mov     rbp, rsp

sub     rsp, 8
push    rdi

lea     rdi, DWORD PTR [rip+0b]
mov     rsi, r15
call    printf

pop     rdi
add     rsp, 8

call    malloc

sub     rsp, 8
push    rax

lea     rdi, DWORD PTR [rip+1b]
mov     rsi, r15
mov     rdx, rax
call    printf

pop     rax
add     rsp, 8

leave
ret

0: .asciz "Thread %u Frees %X\n"
1: .asciz "Thread %u Freed %X\n"
fake_free:
push    rbp
mov     rbp, rsp

sub     rsp, 8
push    rdi

mov     rdx, rdi
lea     rdi, DWORD PTR [rip+0b]
mov     rsi, r15
call    printf

mov     rdi, QWORD PTR [rsp]
call    free

pop     rdx
push    rax

lea     rdi, DWORD PTR [rip+1b]
mov     rsi, r15
call    printf

pop     rax
add     rsp, 8

leave
ret

f:
push    rbp
mov     rbp, rsp

sub     rsp, 8
push    rbx
push    r12
push    r13

mov     eax, 186 # syscall = gettid
syscall          # gettid()
mov     r15, rax

lea     rbx, lock
lea     r12, counter

mov     r13d, 1000000
0:

mov     rdi, rbx
call    queuelock_lock

inc     QWORD PTR [r12]

mov     rdi, rbx
mov     rsi, rax
call    queuelock_unlock

dec     r13d
jne     0b

lea     rbx, finished
lock inc DWORD PTR [rbx]

add     rsp, 8
pop     r13
pop     r12
pop     rbx

xor     eax, eax
leave
ret

#!/usr/bin/python3

from enum import Enum
from sys import stdin
from re import compile

class Action(Enum):
    ALLOCATES = 1
    ALLOCATED = 2
    FREES = 3
    FREED = 4

# Regex patterns
allocates_pattern = compile(r"Thread (\d+) Allocates")
allocated_pattern = compile(r"Thread (\d+) Allocated ([0-9A-Fa-f]+)")
frees_pattern = compile(r"Thread (\d+) Frees ([0-9A-Fa-f]+)")
freed_pattern = compile(r"Thread (\d+) Freed ([0-9A-Fa-f]+)")

actions = {}
allocations = set()
allocations_being_removed = set()

for index, line in enumerate(stdin):
    command = line.strip()
    allocates_match = allocates_pattern.search(command)
    allocated_match = allocated_pattern.search(command)
    frees_match     = frees_pattern.search(command)
    freed_match     = freed_pattern.search(command)
    if allocates_match:
        thread = allocates_match.group(1)
        if thread in actions:
            print(f"Unexpected Allocation in line {index}")
        actions[thread] = Action.ALLOCATES
    elif allocated_match:
        thread = allocated_match.group(1)
        address = allocated_match.group(2)
        if thread not in actions or actions[thread] != Action.ALLOCATES:
            print(f"Unexpected Allocated in line {index}")
        if address in allocations:
            print(f"Unexpected return from malloc in line {index}")
        actions[thread] = Action.ALLOCATED
        allocations.add(address)
    elif frees_match:
        thread = frees_match.group(1)
        address = frees_match.group(2)
        if thread not in actions or actions[thread] != Action.ALLOCATED:
            print(f"Unexpected Frees in line {index}")
        if address not in allocations:
            print(f"Unexpected address passed to free in line {index}")
        actions[thread] = Action.FREES
        allocations.discard(address)
        allocations_being_removed.add((address, thread))
    elif freed_match:
        thread = freed_match.group(1)
        address = freed_match.group(2)
        if thread not in actions or actions[thread] != Action.FREES:
            print(f"Unexpected Freed in line {index}")
        if (address, thread) not in allocations_being_removed:
            print(f"Unexpected free return in line {index}")
        del actions[thread]
        allocations_being_removed.discard((address, thread))
    else:
        print(f"Unexpected Command in line {index}")

./a.out &>1.log
Naruszenie ochrony pamięci (zrzut pamięci)
./validator.py <1.log

cc -Wl,-O9,--gc-sections,--hash-style=sysv,--build-id=none -fmerge-all-constants -fwhole-program -flto -std=c90 -Wall -Wextra -pedantic *.c *.s

malloc(): unaligned tcache chunk detected
Przerwane (zrzut pamięci)

free(): double free detected in tcache 2
Przerwane (zrzut pamięci)

Naruszenie ochrony pamięci (zrzut pamięci)