> For the complete documentation index, see [llms.txt](https://xiayingp.gitbook.io/build_a_os/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiayingp.gitbook.io/build_a_os/lock/untitled-3.md).

# Hardware Support Locking

## Concept

To evaluate whether a lock works, there are three basic criteria: 1. Mutual exclusion 2. Fairness 3. Performance

## Design and Implement Lock

Locks requires OS help. Building spin locks could use: 

1\. `Test-And-Set`. 

2\. `Compare-And-Swap`. 

3\. `Fetch-And-Add`

XV6 uses option 1.

```c
void lock(lock_t *lock) {
  while (TestAndSet(&lock->flag, 1) == 1) ; 
     // spin-wait (do nothing)
}
```

`TestAndSet` swap flag's value with 1, and return the old value. If result is 1, it was locked before, so we spin and wait. If result is 0, it was unlocked, and we locked succesfully, we can now enter the critical section.

## Case Study: Linux-based Futex Locks

### How it works

Mutex lock counter: bit 31 clear means unlocked; bit 31 set means locked.

All code that looks at bit 31 first increases the ‘number of interested threads’ usage counter, which is in bits 0-30. All negative mutex values indicate that the mutex is still locked.

### Code

This code snippet from `lowlevellock.h` in the nptl library (part of the gnu libc library).

```c
void mutex_lock (int *mutex)
{
  unsigned int v;

  /* Bit 31 was clear, we got the mutex.  (this is the fastpath).  */
  if (atomic_bit_test_set (mutex, 31) == 0)
    return;

  atomic_increment (mutex);

  while (1)
    {
      if (atomic_bit_test_set (mutex, 31) == 0)
      {
        atomic_decrement (mutex);
        return;
      }
          /* We have to wait now. First make sure the futex value we are monitoring is truly negative (i.e. locked). */
          v = *mutex;
          if (v >= 0)
            continue;

          lll_futex_wait (mutex, v);
    }
}
```

```c
void mutex_unlock (int *mutex)
{
  /* Adding 0x80000000 to the counter results in 0 if and only if there are not other interested threads - we can return (this is the fastpath).  */
  if (atomic_add_zero (mutex, 0x80000000))
    return;

  /* There are other threads waiting for this mutex, wake one of them up.  */
  lll_futex_wake (mutex, 1);
}
```

### Explain

In `unlock`, `0x80000000` hex is binary: `10 00000 00000 00000 00000 00000 00000` (31 zeros).

`atomic_add_zero` impl is:

```c
# define atomic_add_zero(mem, value)                \
  ({ __typeof (value) __atg13_value = (value);              \
     atomic_exchange_and_add (mem, __atg13_value) == -__atg13_value; })
```

`exchange_and_add` :Add VALUE to *MEM and return the old value of* MEM.

What this function does is: Convert hex value to a proper int. Use negative of value. Compare result of exchange\_and\_add to negative of value, as return result.

The flow of 2 cases: 

![](/files/-M4f059_L0MFf6HEzZeV)

Case 1: If no one waiting, return T. 

Case 2: If someone still waiting, return False.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://xiayingp.gitbook.io/build_a_os/lock/untitled-3.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.