Chapter 43. Isolated data

We can avoid the need to constantly watch out for subtle problems with ref T can be avoided by using Nim’s Isolated[T] type, provided by the module std / isolation. Isolated is a type that has the following declaration and associated routines: type Isolated*[T] = object

  value: T

proc =copyT {.error.} ## Isolated data can only be moved, not copied. proc =sinkT = # delegate to value's sink operation =sink(dest.value, src.value) proc =destroyT = # delegate to value's destroy operation =destroy(dest.value) proc isolateT: Isolated[T] ## Creates an isolated subgraph from the expression value. ## Isolation is checked at compile time. proc unsafeIsolateT: Isolated[T] = ## Creates an isolated subgraph from the expression value. ## Warning: The proc doesn't check whether value is isolated. IsolatedT proc extractT: T = ## Returns the internal value of src. ## The value is moved from src. result = move(src.value)

Construction must ensure that the invariant holds, namely that the wrapped T is free of external aliases into it. To ensure this property, construction must be done via the proc isolate (or via the unchecked unsafe unsafeIsolate proc). The isolate proc is the only operation that needs special language support; it performs an "isolation check". How this isolation check is performed is beyond the scope of the book and the used algorithm is being refined frequently. But a crucial insight is that calls of noSideEffect routines are safe to isolate as long as variables that are of type ref or contain a ref are not used inside the call expression: import std / isolation var global: ref int func identity(x: ref int): ref int = x func select(cond: bool; x, y: ref int): ref int =

(if cond: x else: y)

proc main =

let a = isolate(new(ref int)) 1
let local = new(ref int) 2
let b = isolate(local) 3
global = local 4
let c = isolate select(true, identity(new(ref int)), new(ref int)) 5

1 new(ref int) creates an object on the heap that cannot possibly be aliased

 yet. It is safe to be “isolated”.

2 Once new(ref int) is assigned to the variable local this variable could

 used later on breaking the isolation.

3 Hence isolate(local) produces a compile-time error, saying that local

 cannot be isolated.

4 local is assigned to global which could be used later on to break the

 isolation.

5 Nested calls can be isolated too, as long as the calls are noSideEffect and

 no variables are involved.

In the context of an isolation check, object constructions such as MyRefObject(a: x, b: y) can be treated like routine calls and hence are allowed to be isolated. The Isolated[T] type is powerful enough to model linked lists. The freedom 268 of data races is ensured at compile time. The following program exposes these ideas and uses createThread instead of spawn in order to show that Isolated[T] works with the low-level threading API too: import std / [os, locks, isolation] type MyList {.acyclic.} = ref object 1

  data: string
  next: Isolated[MyList]         2

template withMyLock*(a: Lock, body: untyped) = 3 acquire(a) {.gcsafe.}: 4

 try:
    body
 finally:
    release(a)

var head: Isolated[MyList] 5 var headLock: Lock; initLock headLock 6 proc send(x: sink string) = withMyLock headLock:

  head = isolate MyList(data: x, next: move head) 7

proc worker() {.thread.} = var workItem = MyList(nil) var endReached = false while true:

  withMyLock headLock:
    workItem = extract head 8
    if workItem != nil:
      head = move workItem.next 9
 if workItem.isNil: 10
    if endReached: break
    os.sleep 30 11
 else:
    if workItem.data.len == 0: 12
      endReached = true
    else:
      echo workItem.data

var thr: Thread[void] 13 createThread(thr, worker) send "abc" send "def" send "" joinThread(thr)

1 The node type a linked list consists of. It has to be annotated with acyclic so that the cycle collector does not get involved; it does not support objects that are shared between threads. 2 Instead of the typical next: MyList we declare next to be of type Isolated[MyList] to enforce the invariant that list nodes can only be moved between threads and not copied and so do not require synchronization via atomic instructions or locks. 3 Even though std / locks offers a withLock template we define our own here that adds {.gcsafe.}. 4 Since we seek to use ref freely in the block without triggering the notion of “gcsafety” (see Section 26.5, “GC safety effect”) we wrap the whole block in a {.gcsafe.} environment. 5 The head of the linked list must be of the type Isolated[MyList] in order to be protected by Nim’s type system. 6 Multiple threads access the head of the list potentially at the same time. At runtime head is protected by the headLock lock. 7 Moves the old value of head into the next field of the constructed node and isolates this node. Then this node becomes the new head of the singly linked list. The isolation succeeds because head itself is of type Isolated so uniqueness is preserved as long as it is moved from. 8 While traversing the list in the worker thread we unlink the node that we seek to work on. 9 After this move operation the object that workItem points to is isolated. 10 Since workItem is isolated, we can proceed with the rest of the logic outside of the withMyLock environment. 11 The item is nil and we have not yet reached the stop token, so wait and give the other thread time to send more tasks. 12 As in previous examples we use the empty string to denote a stop token. Due to the singly linked list and the reversing nature of the traversal (both send and receive use the next field) there can be nodes after the stop token. Thus we have as an ending condition: The end token has been received and the traversal arrives at a nil node. 13 The usual plumbing code to setup the worker thread and send it some tasks.

ch43.md 6.3 KB History Raw

Chapter 43. Isolated data

ch43.md 6.3 KB

History Raw