whitequark's lab notebook

Minimizing logic expressions

2020-04-06T17:25:03Z

While working on reverse-engineering the Microchip ATF15xx CPLD family, I found myself deriving minimal logic functions from a truth table. This useful because while it is easy to sample all possible states of a black box combinatorial function using e.g. boundary scan, these truth tables are unwieldy and don’t provide much insight into the hardware. While a minimal function with the same truth table would not necessarily be the function implemented by the hardware (which may have hidden variables, or simply use a larger equivalent function that is more convenient to implement), deriving one still provides great insight. In this note I explore this process.

My chosen approach (thanks to John Regehr for the suggestion) I got for an earlier project is to implement an interpreter for a simple logic expression abstract syntax tree in Racket and then use Rosette to translate assertions about the results of interpreting an arbitrary logic expression, as well as a cost function, into a query for an SMT solver.

Although I could use an off-the-shelf logic minimizer here (like Espresso), most logic minimizers solve a different problem: quickly translating large designs to simple netlists. However, I would like to have a complex output netlist: the ATF15xx CPLDs have a hardware XOR gate that I would like the minimizer to infer on its own. On the other hand, I don’t really care about the runtime of the minimizer as long as it’s on the order of minutes to hours. Rosette’s flexibility is a perfect match for this task.

The following code demonstrates the approach and its ability to derive a XOR gate from3 the input expression. It can be easily modified for a particular application by extending (or reducing, e.g. for translation to an and-inverter graph) the logic language, or altering the cost function.

minlogic.rkt (download)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#lang rosette/safe
(require rosette/lib/angelic
         rosette/lib/match)
(define (^^ x y) (|| (&& x (! y)) (&& (! x) y)))

(struct lnot (a)   #:transparent)
(struct land (a b) #:transparent)
(struct lor  (a b) #:transparent)
(struct lxor (a b) #:transparent)
(struct lvar (v)   #:transparent)
(struct llit (v)   #:transparent)

(define (ldump e)
  (match e
    [(lnot a)   `(! ,(ldump a))]
    [(land a b) `(&& ,(ldump a) ,(ldump b))]
    [(lor  a b) `(\|\| ,(ldump a) ,(ldump b))]
    [(lxor a b) `(^^ ,(ldump a) ,(ldump b))]
    [(lvar v) v]
    [(llit v) v]))

(define (leval e)
  (match e
    [(lnot a)   (!  (leval a))]
    [(land a b) (&& (leval a) (leval b))]
    [(lor  a b) (|| (leval a) (leval b))]
    [(lxor a b) (^^ (leval a) (leval b))]
    [(lvar v) v]
    [(llit v) v]))

(define (lcost e)
  (match e
    [(lnot a)   (+ 1 (lcost a))]
    [(land a b) (+ 2 (lcost a) (lcost b))]
    [(lor  a b) (+ 2 (lcost a) (lcost b))]
    [(lxor a b) (+ 2 (lcost a) (lcost b))]
    [(lvar v) 0]
    [(llit v) 1]))

(define (??lexpr terminals #:depth depth)
  (apply choose*
    (if (<= depth 0) terminals
    (let [(a (??lexpr terminals #:depth (- depth 1)))
          (b (??lexpr terminals #:depth (- depth 1)))]
      (append terminals
        (list (lnot a) (land a b) (lor a b) (lxor a b)))))))

(define (lmincost #:forall inputs #:tactic template #:equiv behavior)
  (define model
    (optimize
      #:minimize  (list (lcost template))
      #:guarantee (assert (forall inputs (equal? (leval template) behavior)))))
  (if (unsat? model) model
      (evaluate template model)))

(define-symbolic a b c boolean?)
(define f
  (lmincost
    #:forall (list a b c)
    #:tactic (??lexpr (list (lvar a) (lvar b) (lvar c) (llit #f)) #:depth 3)
    #:equiv  (&& (|| a (! (&& b c))) (! (&& a (|| (! b) (! c)))))))
(displayln (ldump f)) ; (! (^^ (&& c b) a))

Synthesizing optimal 8051 code

2020-04-06T16:44:20Z

While working on an application targeting Nordic nRF24LE1, a wireless SoC with a fairly slow 8051 core, I was wondering if I can have fast, or at least not unusably slow, cryptography. Most cryptographic algorithms involve wide rotates, and the 8051 only has instructions for rotating a 8-bit accumulator by one bit at a time. In this note I explore deriving optimal code for rotating values in registers (that may be bigger than 8 bits) by multiple bits.

Introduction
Code generator
Results
- 8-bit rotates
- 16-bit rotates

Introduction

My chosen approach (thanks to John Regehr for the suggestion) is to implement an interpreter for an abstract 8051 assembly representation in Racket and then use Rosette to translate assertions about the results of interpreting an arbitrary piece of code into a query for an SMT solver.

Rosette greatly simplifies this task because it lets me avoid learning anything about SMT solvers, and only requires me to understand the constraints of its symbolic execution approach. (Only a small subset of Racket is safe to use in Rosette, and functions outside of that subset are hard to use correctly without an in-depth understaning of how Rosette works.)

Code generator

The following code generates all possible optimal (more on that below) 8-bit and 16-bit rotates. It uses a rather hacky and complicated scheme where it runs several solvers in parallel, one per CPU, each aiming for a particular fixed number of instructions, and then picks the smallest result as the solvers finish. This is because at the time of writing it, I did not understand that Rosette allows optimizing exists-forall problems. (It is quite easy to do so, as I describe in a later note.)

However, that turned out to be a blessing in disguise; when writing this note, I rewrote the query as an optimization problem for the solver, and it doesn’t seem like that would work for this use case. First, of the solvers that can be used by Rosette, only Z3 supports quantified formulas, whereas Boolector had the best performance with the simpler queries. Second, even for very small programs (such as 8-bit rotates, which all fit in 4 instructions, and even restricting the usable registers to 2 out of 8), the memory footprint of Z3 grows extremely quickly, and I always ran out of memory before getting a solution.

By “optimal” here I mean “optimal within the limited model being used”, of course. The model I’m using specifically omits any memory access (preventing the use of the XCHD instruction among other things), and in general has a very limited number of instructions to make solver runtime manageable. It is possible (but unlikely) that some of the instructions missing in the model but present in every 8051 CPU provide a faster way to do rotates. It is possible (and fairly likely) that your specific flavor of 8051 CPU provides a faster way to do rotates that involves memory-mapped I/O; indeed, nRF24LE1 does, but I was interested in more portable code.

synth51.rkt (download)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291

#lang rosette/safe

(require (only-in racket hash in-range for for/list with-handlers flush-output
                  thread thread-wait break-thread exn:break?
                  make-semaphore semaphore-wait semaphore-post call-with-semaphore/enable-break
                  processor-count))
(require rosette/solver/smt/z3
         rosette/solver/smt/boolector
         rosette/solver/smt/yices)
;(current-solver (z3 #:logic 'QF_BV #:options (hash
;   ':parallel.enable 'true
;   ':parallel.threads.max 4)))
;(current-solver (yices #:logic 'QF_BV))
(current-solver (boolector #:logic 'QF_BV))

(require rosette/lib/angelic
         rosette/lib/match)
(current-bitwidth 5)

; bit operations
(define (rotate-right s i x)
  (cond
    [(= i 0) x]
    [else (concat (extract (- i 1) 0 x) (extract (- s 1) i x))]))
(define (rotate-left s i x)
  (cond
    [(= i 0) x]
    [else (concat (extract (- s i 1) 0 x) (extract (- s 1) (- s i) x))]))

(define (replace-bit s i x y)
  (define m (bvshl (bv 1 s) (integer->bitvector i s)))
  (cond
    [(bveq y (bv 0 1)) (bvand x (bvnot m))]
    [(bveq y (bv 1 1)) (bvor x m)]
    [else (assert #f)]))

; CPU state
(struct state (A C Rn) #:mutable #:transparent)

(define (state-Rn-ref S n)
  (vector-ref (state-Rn S) n))
(define (state-Rn-set! S n v)
  (vector-set! (state-Rn S) n v))
(define (state-R0 S) (state-Rn-ref S 0))
(define (state-R1 S) (state-Rn-ref S 1))
(define (state-R2 S) (state-Rn-ref S 2))
(define (state-R3 S) (state-Rn-ref S 3))
(define (state-R4 S) (state-Rn-ref S 4))
(define (state-R5 S) (state-Rn-ref S 5))
(define (state-R6 S) (state-Rn-ref S 6))
(define (state-R7 S) (state-Rn-ref S 7))

(define-symbolic A R0 R1 R2 R3 R4 R5 R6 R7 (bitvector 8))
(define-symbolic C (bitvector 1))
(define (make-state)
  (state A C (vector R0 R1 R2 R3 R4 R5 R6 R7)))

; instructions
(struct MOV-A-Rn (n) #:transparent)
(struct MOV-Rn-A (n) #:transparent)
(struct ANL-A-Rn (n) #:transparent)
(struct ORL-A-Rn (n) #:transparent)
(struct XRL-A-Rn (n) #:transparent)
(struct XCH-A-Rn (n) #:transparent)
(struct MOV-A-i (i) #:transparent)
(struct ANL-A-i (i) #:transparent)
(struct ORL-A-i (i) #:transparent)
(struct SWAP-A () #:transparent)
(struct CLR-C () #:transparent)
(struct MOV-C-An (n) #:transparent)
(struct MOV-An-C (n) #:transparent)
(struct RLC-A () #:transparent)
(struct RRC-A () #:transparent)
(struct RL-A () #:transparent)
(struct RR-A () #:transparent)

(define (print-insn insn)
  (match insn
    [(MOV-A-Rn n) (printf "MOV A, R~s~n" n)]
    [(MOV-Rn-A n) (printf "MOV R~s, A~n" n)]
    [(ANL-A-Rn n) (printf "ANL A, R~s~n" n)]
    [(ORL-A-Rn n) (printf "ORL A, R~s~n" n)]
    [(XRL-A-Rn n) (printf "XRL A, R~s~n" n)]
    [(XCH-A-Rn n) (printf "XCH A, R~s~n" n)]
    [(MOV-A-i i)  (printf "MOV A, #0x~x~n" (bitvector->natural i))]
    [(ANL-A-i i)  (printf "ANL A, #0x~x~n" (bitvector->natural i))]
    [(ORL-A-i i)  (printf "ORL A, #0x~x~n" (bitvector->natural i))]
    [(SWAP-A)     (printf "SWAP A~n")]
    [(CLR-C)      (printf "CLR C~n")]
    [(MOV-C-An n) (printf "MOV C, ACC.~s~n" n)]
    [(MOV-An-C n) (printf "MOV ACC.~s, C~n" n)]
    [(RLC-A)      (printf "RLC A~n")]
    [(RRC-A)      (printf "RRC A~n")]
    [(RL-A)       (printf "RL A~n")]
    [(RR-A)       (printf "RR A~n")]))

; sketches
(define (??insn)
  (define n (choose* 0 1)); 2 3 4 5 6 7))
  (define-symbolic* i (bitvector 8))
  ;(define i (choose* (bv #xf0 8) (bv #x0f 8)))
  (choose* (MOV-A-Rn n)
           (MOV-Rn-A n)
           (ANL-A-Rn n)
           (ORL-A-Rn n)
           (XRL-A-Rn n)
           (XCH-A-Rn n)
           (MOV-A-i i)
           (ANL-A-i i)
           (ORL-A-i i)
           (SWAP-A)
           (CLR-C)
           (MOV-C-An n)
           (MOV-An-C n)
           (RLC-A)
           (RRC-A)
           (RL-A)
           (RR-A)))

(define (??prog fuel)
  (if (= fuel 0) null
      (cons (??insn) (??prog (- fuel 1)))))

; symbolic interpreter
(define (run-insn S insn)
  (match insn
    [(MOV-A-Rn n)
     (set-state-A! S (state-Rn-ref S n))]
    [(MOV-Rn-A n)
     (state-Rn-set! S n (state-A S))]
    [(ANL-A-Rn n)
     (set-state-A! S (bvand (state-A S) (state-Rn-ref S n)))]
    [(ORL-A-Rn n)
     (set-state-A! S (bvor  (state-A S) (state-Rn-ref S n)))]
    [(XRL-A-Rn n)
     (set-state-A! S (bvxor (state-A S) (state-Rn-ref S n)))]
    [(XCH-A-Rn n)
     (let ([A (state-A S)] [Rn (state-Rn-ref S n)])
       (set-state-A! S Rn) (state-Rn-set! S n A))]
    [(MOV-A-i i)
     (set-state-A! S i)]
    [(ANL-A-i i)
     (set-state-A! S (bvand (state-A S) i))]
    [(ORL-A-i i)
     (set-state-A! S (bvor  (state-A S) i))]
    [(SWAP-A)
     (let ([A (state-A S)])
       (set-state-A! S (concat (extract 3 0 A) (extract 7 4 A))))]
    [(CLR-C)
     (set-state-C! S (bv 0 1))]
    [(MOV-C-An n)
     (set-state-C! S (extract n n (state-A S)))]
    [(MOV-An-C n)
     (set-state-A! S (replace-bit 8 n (state-A S) (state-C S)))]
    [(RLC-A)
     (let ([A (state-A S)] [C (state-C S)])
       (set-state-A! S (concat (extract 6 0 A) C))
       (set-state-C! S (extract 7 7 A)))]
    [(RRC-A)
     (let ([A (state-A S)] [C (state-C S)])
       (set-state-A! S (concat C (extract 7 1 A)))
       (set-state-C! S (extract 0 0 A)))]
    [(RL-A)
     (let ([A (state-A S)])
       (set-state-A! S (concat (extract 6 0 A) (extract 7 7 A))))]
    [(RR-A)
     (let ([A (state-A S)])
       (set-state-A! S (concat (extract 0 0 A) (extract 7 1 A))))]
    ))

; program verifier
(define (verify-prog prog asserts)
  (define S  (make-state))
  (define S* (make-state))
  (define solution
    (verify
     #:guarantee
     (begin
       (for-each (curry run-insn S*) prog)
       (asserts S S*))))
  (if (unsat? solution) #t
      (begin
        (displayln (evaluate S  solution))
        (displayln (evaluate S* solution))
        #f)))

; program synthesizer
(define (synthesize-prog sketch asserts)
  (define S  (make-state))
  (define S* (make-state))
  (define solution
    (synthesize
     #:forall S
     #:guarantee
     (begin
       (for-each (lambda (insn) (run-insn S* insn)) sketch)
       (asserts S S*))))
  (if (unsat? solution) #f
      (evaluate sketch solution)))

(define (optimize-prog max-fuel sketch-gen asserts)
  (define (worker fuel)
    (define prog (synthesize-prog (sketch-gen fuel) asserts))
    (if prog
        (begin
          (eprintf "sat! ~s~n" fuel)
          (for-each print-insn prog))
        (begin
          (eprintf "unsat! ~s~n" fuel)
          (if (>= fuel max-fuel) #f
              (worker (+ fuel 1))))))
  (worker 0))

(define (optimize-prog/parallel max-fuel sketch-gen asserts)
  (define solved (box #f))
  (define solved-fuel (box 1000))
  (define threads (box '()))
  (define report-sema (make-semaphore 1))
  (define (worker fuel)
    (cond
      [(or (not (unbox solved)) (< fuel (unbox solved-fuel)))
       (define prog (synthesize-prog (sketch-gen fuel) asserts))
       (call-with-semaphore/enable-break report-sema
        (lambda ()
          (if prog
              (begin
                (eprintf "sat! ~s~n" fuel)
                (for-each (lambda (thd-fuel)
                            (if (> (cdr thd-fuel) fuel)
                                (break-thread (car thd-fuel))
                                (void))) (unbox threads))
                (if (or (not (unbox solved)) (< fuel (unbox solved-fuel)))
                    (begin
                      (set-box! solved-fuel fuel)
                      (set-box! solved prog))
                    (void)))
              (eprintf "unsat! ~s~n" fuel))))]))
  (define core-sema (make-semaphore (processor-count)))
  (for ([fuel (in-range (add1 max-fuel))])
    (semaphore-wait core-sema)
    (define thd
      (thread (lambda ()
                (with-handlers ([exn:break? (lambda (x) (void))])
                  (worker fuel))
                (semaphore-post core-sema))))
    (set-box! threads (cons (cons thd fuel) (unbox threads))))
  (for-each (lambda (thd-fuel) (thread-wait (car thd-fuel))) (unbox threads))
  (if (not (unbox solved)) (void)
      (begin
        (for-each print-insn (unbox solved))
        (flush-output))))

(define (assert-preserve S S* . regs)
  (define (assert-preserve-reg n)
    (assert (bveq (state-Rn-ref S n) (state-Rn-ref S* n))))
  (for-each assert-preserve-reg regs))

; examples
(define (optimize-8b-rotate-right n)
  (optimize-prog/parallel
   4
   (lambda (fuel) (??prog fuel))
   (lambda (S S*)
     (assert (bveq (rotate-right 8 n (state-R0 S)) (state-R0 S*)))
     (assert-preserve S S* 1 2 3 4 5 6 7))))
(for ([n (in-range 8)])
 (time
  (printf "; rotate right R0 by ~a~n" n) (flush-output)
  (optimize-8b-rotate-right n)
  (printf "; ")))

(define (optimize-16b-rotate-right n)
  (optimize-prog/parallel
   20
   (lambda (fuel)
    (if (= fuel 0) '()
      (append
       ; help the synthesizer out a bit
       (list (MOV-A-Rn (choose* 0 1)))
       (??prog fuel)
       (list (MOV-Rn-A (choose* 0 1))))))
   (lambda (S S*)
     (define R10  (concat (state-R1 S ) (state-R0 S )))
     (define R10* (concat (state-R1 S*) (state-R0 S*)))
     (assert (bveq (rotate-right 16 n R10) R10*))
     (assert-preserve S S* 2 3 4 5 6 7))))
(for ([n (in-range 16)])
 (time
  (printf "; rotate right R1:R0 by ~a~n" n) (flush-output)
  (optimize-16b-rotate-right n)
  (printf "; ")))

Results

Generating the optimal 8-bit and 16-bit rotates took about half a day on a modern laptop (Dell XPS13 9360, using all cores and with mitigations disabled). Because of that I have not attempted generating wider ones so far.

8-bit rotates

The following code lists all optimal 8-bit rotates, by 0 to 7 bits.

rot8.asm (download)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

; rotate right R0 by 0
; rotate right R0 by 1
MOV A, R0
RR A
MOV R0, A
; rotate right R0 by 2
MOV A, R0
RR A
RR A
MOV R0, A
; rotate right R0 by 3
XCH A, R0
RL A
SWAP A
MOV R0, A
; rotate right R0 by 4
MOV A, R0
SWAP A
MOV R0, A
; rotate right R0 by 5
MOV A, R0
SWAP A
RR A
XCH A, R0
; rotate right R0 by 6
MOV A, R0
RL A
RL A
MOV R0, A
; rotate right R0 by 7
MOV A, R0
RL A
MOV R0, A

16-bit rotates

The following code lists all optimal 16-bit rotates, by 0 to 15 bits. I find the approach the solver used for the rotate by 10 nothing short of brilliant, and the approach it took for rotate by 3/5/11/13 pretty neat as well.

rot16.asm (download)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

; rotate right R1:R0 by 0
; rotate right R1:R0 by 1
MOV A, R1
MOV C, ACC.0
XCH A, R0
RRC A
XCH A, R0
RRC A
MOV R1, A
; rotate right R1:R0 by 2
MOV A, R1
MOV C, ACC.0
XCH A, R0
RRC A
XCH A, R0
RRC A
MOV C, ACC.0
XCH A, R0
RRC A
XCH A, R0
RRC A
MOV R1, A
; rotate right R1:R0 by 3
MOV A, R0
XRL A, R1
MOV R1, A
ANL A, #0xf8
XRL A, R0
SWAP A
RL A
XCH A, R1
SWAP A
RL A
XRL A, R1
MOV R0, A
; rotate right R1:R0 by 4
MOV A, R0
XRL A, R1
ANL A, #0xf0
XCH A, R1
XRL A, R1
SWAP A
XCH A, R0
XRL A, R1
SWAP A
MOV R1, A
; rotate right R1:R0 by 5
MOV A, R1
XRL A, R0
ANL A, #0x1f
XCH A, R0
XRL A, R0
RR A
SWAP A
XCH A, R0
XRL A, R1
SWAP A
RR A
MOV R1, A
; rotate right R1:R0 by 6
MOV A, R1
RLC A
XCH A, R0
RLC A
XCH A, R1
RLC A
MOV C, ACC.7
XCH A, R1
RLC A
XCH A, R1
RLC A
MOV R0, A
; rotate right R1:R0 by 7
MOV A, R0
MOV C, ACC.7
MOV A, R1
RLC A
XCH A, R0
RLC A
MOV R1, A
; rotate right R1:R0 by 8
MOV A, R1
XCH A, R0
MOV R1, A
; rotate right R1:R0 by 9
MOV A, R1
RRC A
MOV A, R0
RRC A
XCH A, R1
RRC A
MOV R0, A
; rotate right R1:R0 by 10
MOV A, R1
XRL A, R0
ANL A, #0x3
XRL A, R1
RR A
RR A
XCH A, R0
XRL A, R1
RR A
RR A
XRL A, R0
MOV R1, A
; rotate right R1:R0 by 11
MOV A, R1
XRL A, R0
MOV R1, A
ANL A, #0x7
XRL A, R0
RL A
SWAP A
XCH A, R1
RL A
SWAP A
XRL A, R1
MOV R0, A
; rotate right R1:R0 by 12
MOV A, R0
XRL A, R1
ANL A, #0xf0
XCH A, R1
XRL A, R1
SWAP A
XCH A, R1
XRL A, R0
SWAP A
MOV R0, A
; rotate right R1:R0 by 13
MOV A, R1
XRL A, R0
ANL A, #0xe0
XCH A, R0
XRL A, R0
SWAP A
RR A
XCH A, R0
XRL A, R1
RR A
SWAP A
MOV R1, A
; rotate right R1:R0 by 14
MOV A, R1
MOV C, ACC.7
XCH A, R0
RLC A
XCH A, R0
RLC A
MOV C, ACC.7
XCH A, R0
RLC A
XCH A, R0
RLC A
MOV R1, A
; rotate right R1:R0 by 15
MOV A, R1
MOV C, ACC.7
XCH A, R0
RLC A
XCH A, R0
RLC A
MOV R1, A

Undocumented nRF24LU1+ quirks

2020-01-27T23:48:52Z

While working with nRF24LU1+, I discovered that the chip has lots and lots of odd corners that are sparsely or strangely documented, where the silicon doesn’t match documentation, etc.

Info page size
Reading info page from MCU
Bootloader and reset vector

Info page size

The datasheet describes the info page as 512 bytes long. However, setting FSR.INFEN and reading the entire address space reveals a 1024 byte periodic structure. The second half appears to be a ROM (it cannot be either programmed or erased), and on my chip it starts with 43 46 54 39 32 32 11 41 2c (“CFT922”) and has an additional 00 at offset 0x21.

Reading info page from MCU

The datasheet describes in detail how to read info page via SPI, and that works just fine. However, it doesn’t explain how to read it via MCU, which is strange because the info page contains an unique chip ID and it is avilable for user data. The FSR.INFEN bit is documented only to affect SPI accesses, for which a diagram implies the info page replaces the 0th page (0x0000..0x0100).

In practice, it works rather differently. Setting FSR.INFEN in firmware replaces all data accesses to flash address space (which is the entire lower half of it) with info page accesses, similar to the previous section. However, code accesses are not affected.

In terms of the 8051 instruction set, MOVC always performs a code access, and MOVX can perform either a data (0) or a code (1) access depending on the state of PCON.PMW bit. PMW stands for “program memory write”, but, in spite of that name, it affects reads too. Because nRF24LU1+ has non-overlapping code and data spaces (besides the info page quirk) there are no references to it in the documentation for that chip, but the documentation for nRF24LE1, which does have overlapping address spaces, is more suggestive.

This means that the info page may be read via the MCU by setting PCON.PMW and FSR.INFEN to make compiler-emitted MOVX instructions work as expected, and then temporarily clearing PCON.PMW each time a byte of the info page is read.

Bootloader and reset vector

The nRF24LU1+ flash is clearly designed for atomic firmware updates: the population count of the 16 bytes at the top of the flash determines whether the bootloader (“protected area”) or application (“unprotected area”) is executed at reset. Thus, it is expected that the application and bootloader take turns programming single bits, which will succeed under worst case power failure.

However, it is useful to have a permanent bootloader mode, where the chip can be programmed via USB by using a strap pin, or a delay and a special USB request. To achieve this, a single bit may be programmed at the top of flash, with the bootloader running the application if the firmware update trigger is not present.

Unfortunately, branching to address 0 doesn’t work; it just causes the bootloader to be re-entered. The datasheet opaquely alludes to this:

Note: In a program running in a protected flash area, movc may not be used to access addresses 0x00 to 0x03.

By using MOVC to access those bytes, it can be seen that, rather than changing the address of the reset vector of the MCU (or for that matter the interrupt vector table; interrupts may not be used in the bootloader), the designers of this chip decided to replace code accesses to the reset vector with a procedurally generated instruction; when FSR.STP is enabled, the first four bytes of the code address space are replaced with 02 XX YY 00, where XX YY is the address of the first protected page. This decodes to LJMP #XXYYh; NOP.

Most 8051 MCUs use an interrupt vector table with 3 bytes per entry, which in practice means that it is usually densely filled with LJMP instructions. (However, there are other possibilities, e.g. sdcc may emit AJMP.) That means that it is practical for a bootloader to read out an instruction, recognize an LJMP (and perhaps a few others) and interpret it, i.e. jump to the address within.

Unfortunately, there is a problem with this approach, which is that even once the application is running, the FSR.STP bit is still set, and this corrupts the first byte of the first interrupt vector (timer 0 overflow). This may be worked around by placing a right-aligned SJMP or AJMP there. Similarly, if no interrupts are used, the linker may place CRT startup code there, which may be worked around with a dummy interrupt handler. In both cases it is necessary to modify the application firmware; there is nothing the bootloader can do here as FSR.STP can not be cleared.

Pixel Pawn wireless flash trigger on-air protocol

2020-01-25T18:43:35Z

In this note I describe the on-air protocol of Pixel Pawn wireless flash trigger.

Tools and methods
Framing
Channels
Commands
Communication

Tools and methods

To interact with the flash trigger, I used Lime Microsystems LimeSDR Mini. To determine the center frequency of transmissions, I used SDRAngel in spectrogram mode, knowing that the device is advertised to work in the 2.4 GHz range. To determine bit rate, modulation, and packet format, I used Universal Radio Hacker as described in its documentation. To understand commands better, I used the Glasgow debug tool’s radio-nrf24l applet in transmit and receive mode as described below.

Framing

Modulation GMSK, data rate 250 kbps, on-air time 356.00 µs, of which settling time 60.75 µs, transmission time 295.25 µs. Packet format:

1010101010101010101010101010101010101100001101010111111001001110101-1100000
<                        67 fixed bits                            > < CMD >

Each button press produces a burst of 5-10 packets. However, holding a button or being in an active mode only produces a single packet every few hundred ms.

Channels

The channel to frequency mapping is as follows:

Channel	Frequency
`HHHH`	2.4020
`HHHL`	2.4065
`HHLH`	2.4100
`HHLL`	2.4185
`HLHH`	2.4210
`HLHL`	2.4295
`HLLH`	2.4355
`HLLL`	2.4385
`LHHH`	2.4450
`LHHL`	2.4465
`LHLH`	2.4515
`LHLL`	2.4600
`LLHH`	2.4620
`LLHL`	2.4695
`LLLH`	2.4710
`LLLL`	2.4770

Commands

Commands are specified in 7 last bits of the packet.

Command	Encoding	Condition
wakeup	`1100000`	power on, mode switch, other command prefix
autofocus	`0001111`	half press
normal release	`0010100`	mode 1 press
shutter open	`0010000`	mode 2 first press
shutter close	`0011011`	mode 2 second press
timer start	`1100100`	mode 3 first press
timer cancel	`0011011`	mode 3 second press

The preamble can be quite short, as few as 2 octets long. However, commands that are not preceded by 1100000 will be often not recognized, regardless of preamble length.

Communication

Considering the framing, any appropriately encoded octet sequence that includes the following one will trigger a command:

aa aa aa aa b0 d5 f9 3a (80|CMD)

An elegant way to emulate a transmitter is to use an nRF24L01(+) in nRF2401 compatible mode with 4 address bytes set to aa aa aa aa and data bytes set to b0 d5 f9 3a (80|CMD). However, in a pinch, just transmitting this as a kind of in-band signal in any other packet framing also works just fine.

Similarly, an elegant way to emulate a receiver is to use an nRF24L01(+) in nRF2401 compatible mode with 4 address bytes set to b0 d5 f9 3a. (It uses the same aa preamble, and synchronizes to address bytes.)

nRF24L01(+) only support channel frequencies of integer MHz; this flash trigger uses some channels of half-integer MHz, e.g. 2.4465. The nRF24L01(+) is promiscuous enough that it easily and reliably locks to transmissions on half-integer MHz channels. However, the flash trigger receiver configured to use such a channel ignores any transmissions half MHz apart. This means that an nRF24L01(+) can only transmit on half of the defined channels.

One could notice that nRF24L01(+) transmits with its PLL in open loop, and the frequency of said PLL drifts down. By issuing the REUSE_TX_PL command and pulsing CE for a few ms, it will transmit the last command in a loop while drifting down, and eventually hitting the right frequency. This, however, is a rather disgusting workaround.

Patching nVidia GPU driver for hot-unplug on Linux

2018-10-28T08:27:37Z

Recently, I’ve using an extremely cursed setup where my XPS 13 9360 laptop is connected to a Sonnet EchoExpress 2 box rewired for Thunderbolt 3 that has an nVidia Quadro 600 GPU, and Linux is set up for render offload to the eGPU and then frame transfer back to iGPU to be displayed on the laptop’s integrated display, which (to my sheer surprise) not only works quire reliably, but even gives me higher FPS in Team Fortress 2 than the iGPU.

There’s only really one downside: if the eGPU falls off the bus, either because someone™ pulled out the cable, or because the stars didn’t align quite right this morning and it decided to enumerate seemingly at random (sometimes this is preceeded by whining from PCIe AER, sometimes not, I think it’s some sort of hardware issue like a badly inserted PCIe card, but I’m not entirely sure), the nVidia driver… hangs. Hangs quite deliberately, as the sources to the kernel driver show. This leaves the Xorg instance bound to the eGPU hung forever (which confuses bumblebee, but is otherwise not especially bad), and also prevents any new ones from using the eGPU (which is bad).

Anyway, I was kind of annoyed of rebooting every time it happens, so I decided to reboot a few more dozen times instead while patching the driver. This has indeed worked, and left me with something similar to a functional hot-unplug, mildly crippled by the fact that nvidia-modeset is a completely opaque blob that keeps some internal state and tries to act on it, getting stuck when it tries to do something to the now-missing eGPU.

Turns out, there are only a few issues preventing functional hot-unplug.

In nvidia_remove, the driver actually checks if anyone’s still trying to use it, and if yes, it tries to just hang the removal process. This doesn’t actually work, or rather, it mostly works by accident. It starts an infinite loop calling os_schedule() while having taken the NV_LINUX_DEVICES lock. While in the default configuration this indeed hangs any reentrant requests into the driver by virtue of NV_CHECK_PCI_CONFIG_SPACE taking the same lock (in verify_pci_bars, passing the NVreg_CheckPCIConfigSpace=0 module option eliminates that accidental safety mechanism, and allows reentrant requests to proceed. They do not crash due to memory being deallocated in nvidia_remove (so you don’t get an unhandled kernel page fault), but they still crash due to being unable to access the GPU.
The NVKMS component (in the nvidia-modeset module) tries to maintain some state, and change it when e.g. the Xorg instance quits and closes the /dev/nvidia-modeset file. Unfortunately, it does not expect the GPU to go away, and first spews a few messages to dmesg similar to nvidia-modeset: ERROR: GPU:0: Failed to query display engine channel state: 0x0000857d:0:0:0x0000000f, after which it appears to hang somewhere inside the blob, which has been conveniently stripped of all symbols. This needs to be prevented, but…
The NVKMS component effectively only exposes a single opaque ioctl, and all the communication, including communication of the GPU bus ID, happens out of band with regards to the open source parts of the nvidia-modeset module. Fortunately, NVKMS calls back into NVRM, and this allows us to associate each /dev/nvidia-modeset fd with the GPU bus ID.
When unloading NVKMS, it also tries to act on its internal state and change the GPU state, which leads to the same hang.

All in all, this allows a patch to be written that detects when a GPU goes away, ignores all further NVKMS requests related to that specific GPU (and returns -ENOENT in response to ioctls, which Xorg appropriately interprets as a fault condition), correctly releases the resources by requesting NVRM, and improperly unloads NVKMS so it doesn’t try to reset the GPU state. (All actual resources should be released by this point, and NVKMS doesn’t have any resource allocation callbacks other than those we already intercept, so in theory this doesn’t have any bad consequences. But I’m not working for nVidia, so this might be completely wrong.)

After the GPU is plugged back in, NVKMS will try to act on its internal state again; in this case, it doesn’t hang, but it doesn’t initialize the GPU correctly either, so the nvidia-modeset kernel module has to be (manually) reloaded. It’s not easy to do this automatically because in a hypothetical system with more than one nVidia GPU the module would still be in use when one of them dies, and so just hard reloading NVKMS would have unfortunate consequences. (Though, I don’t really know whether NVKMS would try to access the dead GPU in response to the request acting on the other GPU anyway. I decided to do it conservatively.) Once it’s reloaded you’re back in the game though!

Here’s the patch, written against the nvidia-legacy-390xx-390.87 Debian source package:

nvidia-hot-gpu-on-gpu-unplug-action.patch (download)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387

diff -ur original/common/inc/nv-linux.h patchedl/common/inc/nv-linux.h
--- original/common/inc/nv-linux.h	2018-09-23 12:20:02.000000000 +0000
+++ patched/common/inc/nv-linux.h	2018-10-28 07:19:21.526566940 +0000
@@ -1465,6 +1465,7 @@
 typedef struct nv_linux_state_s {
     nv_state_t nv_state;
     atomic_t usage_count;
+    atomic_t dead;
 
     struct pci_dev *dev;
 
diff -ur original/common/inc/nv-modeset-interface.h patched/common/inc/nv-modeset-interface.h
--- original/common/inc/nv-modeset-interface.h	2018-08-22 00:55:23.000000000 +0000
+++ patched/common/inc/nv-modeset-interface.h	2018-10-28 07:22:00.768238371 +0000
@@ -25,6 +25,8 @@
 
 #include "nv-gpu-info.h"
 
+#include <asm/atomic.h>
+
 /*
  * nvidia_modeset_rm_ops_t::op gets assigned a function pointer from
  * core RM, which uses the calling convention of arguments on the
@@ -115,6 +117,8 @@
 
     int (*set_callbacks)(const nvidia_modeset_callbacks_t *cb);
 
+    atomic_t * (*gpu_dead)(NvU32 gpu_id);
+
 } nvidia_modeset_rm_ops_t;
 
 NV_STATUS nvidia_get_rm_ops(nvidia_modeset_rm_ops_t *rm_ops);
diff -ur original/common/inc/nv-proto.h patched/common/inc/nv-proto.h
--- original/common/inc/nv-proto.h	2018-08-22 00:55:23.000000000 +0000
+++ patched/common/inc/nv-proto.h	2018-10-28 07:20:49.939494812 +0000
@@ -81,6 +81,7 @@
 NvBool      nvidia_get_gpuid_list       (NvU32 *gpu_ids, NvU32 *gpu_count);
 int         nvidia_dev_get              (NvU32, nvidia_stack_t *);
 void        nvidia_dev_put              (NvU32, nvidia_stack_t *);
+atomic_t *  nvidia_dev_dead             (NvU32);
 int         nvidia_dev_get_uuid         (const NvU8 *, nvidia_stack_t *);
 void        nvidia_dev_put_uuid         (const NvU8 *, nvidia_stack_t *);
 int         nvidia_dev_get_pci_info     (const NvU8 *, struct pci_dev **, NvU64 *, NvU64 *);
diff -ur original/nvidia/nv.c patched/nvidia/nv.c
--- original/nvidia/nv.c	2018-09-23 12:20:02.000000000 +0000
+++ patched/nvidia/nv.c	2018-10-28 07:48:05.895025112 +0000
@@ -1944,6 +1944,12 @@
     unsigned int i;
     NvBool bRemove = NV_FALSE;
 
+    if (NV_ATOMIC_READ(nvl->dead))
+    {
+        nv_printf(NV_DBG_ERRORS, "NVRM: nvidia_close called on dead device by pid %d!\n",
+                  current->pid);
+    }
+
     NV_CHECK_PCI_CONFIG_SPACE(sp, nv, TRUE, TRUE, NV_MAY_SLEEP());
 
     /* for control device, just jump to its open routine */
@@ -2106,6 +2112,12 @@
     size_t arg_size;
     int arg_cmd;
 
+    if (NV_ATOMIC_READ(nvl->dead))
+    {
+        nv_printf(NV_DBG_ERRORS, "NVRM: nvidia_ioctl called on dead device by pid %d!\n",
+                  current->pid);
+    }
+
     nv_printf(NV_DBG_INFO, "NVRM: ioctl(0x%x, 0x%x, 0x%x)\n",
         _IOC_NR(cmd), (unsigned int) i_arg, _IOC_SIZE(cmd));
 
@@ -3217,6 +3229,7 @@
     NV_INIT_MUTEX(&nvl->ldata_lock);
 
     NV_ATOMIC_SET(nvl->usage_count, 0);
+    NV_ATOMIC_SET(nvl->dead, 0);
 
     if (!rm_init_event_locks(sp, nv))
         return NV_FALSE;
@@ -4018,14 +4031,38 @@
         nv_printf(NV_DBG_ERRORS,
                   "NVRM: Attempting to remove minor device %u with non-zero usage count!\n",
                   nvl->minor_num);
+        nv_printf(NV_DBG_ERRORS,
+                  "NVRM: YOLO, waiting for usage count to drop to zero\n");
         WARN_ON(1);
 
-        /* We can't continue without corrupting state, so just hang to give the
-         * user some chance to do something about this before reboot */
-        while (1)
+        NV_ATOMIC_SET(nvl->dead, 1);
+
+        /* Insanity check: wait until all clients die, then hope for the best. */
+        while (1) {
+            UNLOCK_NV_LINUX_DEVICES();
             os_schedule();
-    }
+            LOCK_NV_LINUX_DEVICES();
+
+            nvl = pci_get_drvdata(dev);
+            if (!nvl || (nvl->dev != dev))
+            {
+                goto done;
+            }
+
+            if (NV_ATOMIC_READ(nvl->usage_count) == 0)
+            {
+                break;
+            }
+        }
 
+        nv_printf(NV_DBG_ERRORS,
+                  "NVRM: Usage count is now zero, proceeding to remove the GPU\n");
+        nv_printf(NV_DBG_ERRORS,
+                  "NVRM: This is not actually supposed to work lol. Hope it does tho 👍\n");
+        nv_printf(NV_DBG_ERRORS,
+                  "NVRM: You probably want to reload nvidia-modeset now if you want any "
+                  "of this to ever start up again, but like, man, that's your choice entirely\n");
+    }
     nv = NV_STATE_PTR(nvl);
     if (nvl == nv_linux_devices)
         nv_linux_devices = nvl->next;
@@ -4712,6 +4749,22 @@
     up(&nvl->ldata_lock);
 }
 
+atomic_t *nvidia_dev_dead(NvU32 gpu_id)
+{
+    nv_linux_state_t *nvl;
+    atomic_t *ret;
+
+    /* Takes nvl->ldata_lock */
+    nvl = find_gpu_id(gpu_id);
+    if (!nvl)
+        return NV_FALSE;
+
+    ret = &nvl->dead;
+    up(&nvl->ldata_lock);
+
+    return ret;
+}
+
 /*
  * Like nvidia_dev_get but uses UUID instead of gpu_id. Note that this may
  * trigger initialization and teardown of unrelated devices to look up their
diff -ur original/nvidia/nv-modeset-interface.c patched/nvidia/nv-modeset-interface.c
--- original/nvidia/nv-modeset-interface.c	2018-08-22 00:55:22.000000000 +0000
+++ patched/nvidia/nv-modeset-interface.c	2018-10-28 07:20:25.959243110 +0000
@@ -114,6 +114,7 @@
         .close_gpu      = nvidia_dev_put,
         .op             = rm_kernel_rmapi_op, /* provided by nv-kernel.o */
         .set_callbacks  = nvidia_modeset_set_callbacks,
+        .gpu_dead       = nvidia_dev_dead,
     };
 
     if (strcmp(rm_ops->version_string, NV_VERSION_STRING) != 0)
diff -ur original/nvidia/nv-reg.h patched/nvidia/nv-reg.h
diff -ur original/nvidia-modeset/nvidia-modeset-linux.c patched/nvidia-modeset/nvidia-modeset-linux.c
--- original/nvidia-modeset/nvidia-modeset-linux.c	2018-09-23 12:20:02.000000000 +0000
+++ patched/nvidia-modeset/nvidia-modeset-linux.c	2018-10-28 07:47:14.738703417 +0000
@@ -75,6 +75,9 @@
 
 static struct semaphore nvkms_lock;
 
+static NvU32 clopen_gpu_id;
+static NvBool leak_on_unload;
+
 /*************************************************************************
  * NVKMS executes queued work items on a single kthread.
  *************************************************************************/
@@ -89,6 +92,9 @@
 struct nvkms_per_open {
     void *data;
 
+    NvU32 gpu_id;
+    atomic_t *gpu_dead;
+
     enum NvKmsClientType type;
 
     union {
@@ -711,6 +717,9 @@
     nvidia_modeset_stack_ptr stack = NULL;
     NvBool ret;
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "nvkms_open_gpu called with %08x, pid %d\n",
+           gpuId, current->pid);
+
     if (__rm_ops.alloc_stack(&stack) != 0) {
         return NV_FALSE;
     }
@@ -719,6 +728,10 @@
 
     __rm_ops.free_stack(stack);
 
+    if (ret) {
+        clopen_gpu_id = gpuId;
+    }
+
     return ret;
 }
 
@@ -726,12 +739,17 @@
 {
     nvidia_modeset_stack_ptr stack = NULL;
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "nvkms_close_gpu called with %08x, pid %d\n",
+           gpuId, current->pid);
+
     if (__rm_ops.alloc_stack(&stack) != 0) {
         return;
     }
 
     __rm_ops.close_gpu(gpuId, stack);
 
+    clopen_gpu_id = gpuId;
+
     __rm_ops.free_stack(stack);
 }
 
@@ -771,8 +789,14 @@
 
     popen->type = type;
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "entering nvkms_open_common, pid %d\n",
+           current->pid);
+
     *status = down_interruptible(&nvkms_lock);
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "taken lock in nvkms_open_common, pid %d\n",
+           current->pid);
+
     if (*status != 0) {
         goto failed;
     }
@@ -781,6 +805,9 @@
 
     up(&nvkms_lock);
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "given up lock in nvkms_open_common, pid %d\n",
+           current->pid);
+
     if (popen->data == NULL) {
         *status = -EPERM;
         goto failed;
@@ -799,10 +826,16 @@
 
     *status = 0;
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "exiting in nvkms_open_common, pid %d\n",
+           current->pid);
+
     return popen;
 
 failed:
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "error in nvkms_open_common, pid %d\n",
+           current->pid);
+
     nvkms_free(popen, sizeof(*popen));
 
     return NULL;
@@ -816,14 +849,36 @@
      * mutex.
      */
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "entering nvkms_close_common, pid %d\n",
+           current->pid);
+
     down(&nvkms_lock);
 
-    nvKmsClose(popen->data);
+    printk(KERN_INFO NVKMS_LOG_PREFIX "taken lock in nvkms_close_common, pid %d\n",
+           current->pid);
+
+    if (popen->gpu_id != 0 && atomic_read(popen->gpu_dead) != 0) {
+        printk(KERN_ERR NVKMS_LOG_PREFIX "awwww u need cleanup :3 "
+               "in nvkms_close_common, pid %d\n",
+               current->pid);
+
+        nvkms_close_gpu(popen->gpu_id);
+
+        popen->gpu_id = 0;
+        popen->gpu_dead = NULL;
+
+        leak_on_unload = NV_TRUE;
+    } else {
+        nvKmsClose(popen->data);
+    }
 
     popen->data = NULL;
 
     up(&nvkms_lock);
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "given up lock in nvkms_close_common, pid %d\n",
+           current->pid);
+
     if (popen->type == NVKMS_CLIENT_KERNEL_SPACE) {
         /*
          * Flush any outstanding nvkms_kapi_event_kthread_q_callback() work
@@ -844,6 +899,9 @@
     }
 
     nvkms_free(popen, sizeof(*popen));
+
+    printk(KERN_INFO NVKMS_LOG_PREFIX "exiting nvkms_close_common, pid %d\n",
+           current->pid);
 }
 
 int NVKMS_API_CALL nvkms_ioctl_common
@@ -855,20 +913,58 @@
     int status;
     NvBool ret;
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "entering nvkms_ioctl_common, pid %d\n",
+           current->pid);
+
     status = down_interruptible(&nvkms_lock);
     if (status != 0) {
         return status;
     }
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "taken lock in nvkms_ioctl_common, pid %d\n",
+           current->pid);
+
+    if (popen->gpu_id != 0 && atomic_read(popen->gpu_dead) != 0) {
+        goto dead;
+    }
+
+    clopen_gpu_id = 0;
+
     if (popen->data != NULL) {
         ret = nvKmsIoctl(popen->data, cmd, address, size);
     } else {
         ret = NV_FALSE;
     }
 
+    if (clopen_gpu_id != 0) {
+        if (!popen->gpu_id) {
+            printk(KERN_INFO NVKMS_LOG_PREFIX "detected gpu %08x open in nvkms_ioctl_common, "
+                   "pid %d\n", clopen_gpu_id, current->pid);
+            popen->gpu_id = clopen_gpu_id;
+            popen->gpu_dead = __rm_ops.gpu_dead(clopen_gpu_id);
+        } else {
+            printk(KERN_INFO NVKMS_LOG_PREFIX "detected gpu %08x close in nvkms_ioctl_common, "
+                   "pid %d\n", clopen_gpu_id, current->pid);
+            popen->gpu_id = 0;
+            popen->gpu_dead = NULL;
+        }
+    }
+
     up(&nvkms_lock);
 
+    printk(KERN_INFO NVKMS_LOG_PREFIX "given up lock in nvkms_ioctl_common, pid %d\n",
+           current->pid);
+
     return ret ? 0 : -EPERM;
+
+dead:
+    up(&nvkms_lock);
+
+    printk(KERN_ERR NVKMS_LOG_PREFIX "*notices ur gpu is dead* owo whats this "
+           "in nvkms_ioctl_common, pid %d\n",
+           current->pid);
+
+    return -ENOENT;
 }
 
 /*************************************************************************
@@ -1239,9 +1335,14 @@
 
     nvkms_proc_exit();
 
-    down(&nvkms_lock);
-    nvKmsModuleUnload();
-    up(&nvkms_lock);
+    if(leak_on_unload) {
+        printk(KERN_ERR NVKMS_LOG_PREFIX "im just gonna leak all the kms junk ok? "
+               "haha nvm wasnt a question. in nvkms_exit\n");
+    } else {
+        down(&nvkms_lock);
+        nvKmsModuleUnload();
+        up(&nvkms_lock);
+    }
 
     /*
      * At this point, any pending tasks should be marked canceled, but

Here’s some handy scripts I was using while debugging it:

insmod.sh


1
2
3
4
5

#!/bin/sh -ex
modprobe acpi_ipmi
insmod nvidia.ko NVreg_ResmanDebugLevel=-1 NVreg_CheckPCIConfigSpace=0
insmod nvidia-modeset.ko
dmesg -w

rmmod.sh


1
2
3

#!/bin/sh
rmmod nvidia-modeset
rmmod nvidia

xorg.sh


1
2

#!/bin/sh
exec Xorg :8 -config /etc/bumblebee/xorg.conf.nvidia -configdir /etc/bumblebee/xorg.conf.d -sharevts -nolisten tcp -noreset -verbose 3 -isolateDevice PCI:06:00:0 -modulepath /usr/lib/nvidia/nvidia,/usr/lib/xorg/modules

And finally, here are the relevant kernel and Xorg log messages, showing what happens when a GPU is unplugged:

dmesg.log


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

[  219.524218] NVRM: loading NVIDIA UNIX x86_64 Kernel Module  390.87  Tue Aug 21 12:33:05 PDT 2018 (using threaded interrupts)
[  219.527409] nvidia-modeset: Loading NVIDIA Kernel Mode Setting Driver for UNIX platforms  390.87  Tue Aug 21 16:16:14 PDT 2018
[  224.780721] nvidia-modeset: nvkms_open_gpu called with 00000600, pid 4560
[  224.807370] nvidia-modeset: detected gpu 00000600 open in nvkms_ioctl_common, pid 4560
[  239.061383] NVRM: GPU at PCI:0000:06:00: GPU-9fe1319c-8dd3-44e4-2b74-de93f8b02c6a
[  239.061387] NVRM: Xid (PCI:0000:06:00): 79, GPU has fallen off the bus.
[  239.061389] NVRM: GPU at 0000:06:00.0 has fallen off the bus.
[  239.061398] NVRM: A GPU crash dump has been created. If possible, please run
               NVRM: nvidia-bug-report.sh as root to collect this data before
               NVRM: the NVIDIA kernel module is unloaded.
[  240.209498] NVRM: Attempting to remove minor device 0 with non-zero usage count!
[  240.209501] NVRM: YOLO, waiting for usage count to drop to zero
[  241.433499] nvidia-modeset: *notices ur gpu is dead* owo whats this in nvkms_ioctl_common, pid 4560
[  241.433851] nvidia-modeset: awwww u need cleanup :3 in nvkms_close_common, pid 4560
[  241.433853] nvidia-modeset: nvkms_close_gpu called with 00000600, pid 4560
[  250.440498] NVRM: Usage count is now zero, proceeding to remove the GPU
[  250.440513] NVRM: This is not actually supposed to work lol. Hope it does tho 👍
[  250.440520] NVRM: You probably want to reload nvidia-modeset now if you want any of this to ever start up again, but like, man, that's your choice entirely
[  250.440870] pci 0000:06:00.1: Dropping the link to 0000:06:00.0
[  250.440950] pci_bus 0000:06: busn_res: [bus 06] is released
[  250.440982] pci_bus 0000:07: busn_res: [bus 07-38] is released
[  250.441012] pci_bus 0000:05: busn_res: [bus 05-38] is released
[  251.000794] pci_bus 0000:02: Allocating resources
[  251.001324] pci_bus 0000:02: Allocating resources
[  253.765953] pcieport 0000:00:1c.0: AER: Corrected error received: 0000:00:1c.0
[  253.765969] pcieport 0000:00:1c.0: PCIe Bus Error: severity=Corrected, type=Physical Layer, (Receiver ID)
[  253.765976] pcieport 0000:00:1c.0:   device [8086:9d10] error status/mask=00002001/00002000
[  253.765982] pcieport 0000:00:1c.0:    [ 0] Receiver Error         (First)
[  253.841064] pcieport 0000:02:02.0: Refused to change power state, currently in D3
[  253.843882] pcieport 0000:02:00.0: Refused to change power state, currently in D3
[  253.846177] pci_bus 0000:03: busn_res: [bus 03] is released
[  253.846248] pci_bus 0000:04: busn_res: [bus 04-38] is released
[  253.846300] pci_bus 0000:39: busn_res: [bus 39] is released
[  253.846348] pci_bus 0000:02: busn_res: [bus 02-39] is released
[  353.369487] nvidia-modeset: im just gonna leak all the kms junk ok? haha nvm wasnt a question. in nvkms_exit
[  357.600350] nvidia-modeset: Loading NVIDIA Kernel Mode Setting Driver for UNIX platforms  390.87  Tue Aug 21 16:16:14 PDT 2018

Xorg.8.log


1

[   244.798] (EE) NVIDIA(GPU-0): WAIT (2, 8, 0x8000, 0x000011f4, 0x00001210)

Game Boy Advance cartridge "SMC805-2 VER:1.5"

2018-09-17T11:02:33Z

I have been asked to determine if a (pirate) Game Boy Advance cartridge with the PCB marked “SMC805-2 VER:1.5 2006.11.16” can be reflashed. The cartridge contains a battery, an ASIC in a chip-on-board package (epoxy blob), an unidentified Intel chip marked “RL0ZAA00” (possibly “RLOZAA00” or “RLOZAAOO”) “A5367952” “Z37LA59B” in a VFBGA-56 package, an ISSI (neé ICSI) static RAM IS62LV1024LL-55H in a TSOP-32 package, and miscellaneous passives.

Front side of the board with the cartridge pins annotated (zoomable version):

It was immediately clear that the Intel chip has to be a Flash, it has a parallel interface, and by looking at it at a shallow angle to the PCB, it could be seen that the balls are laid out in a 7x8 grid. It was then a matter of a search query to discover that an Intel parallel flash in a BGA-56 package belongs to the 28F series, similar to 28F128Kxx.

After desoldering the chip, I have traced the test points to the balls they are connected to, and the pinout matched the 28F series perfectly. Test point assignment (zoomable version):

Note that the Flash interface is completely independent from the cartridge interface; every Flash interface data signal goes through the ASIC.

It is not clear if the Flash interface is tristated by the ASIC when not in use, or by some other method, such as the J1-J2 switch.

Z144SN005 LCD microphotography

2018-08-02T05:50:10Z

I’ve been provided a Z144SN005 LCD that has split in halves as a result of excess mechanical force. Z144SN005 is a ST7735S-based LCD organized as 128RGB×128; it has 384 sources and 128 gates. I took some microphotographs of it using an Amscope ME300TZ-2L-3M metallurgical microscope.

The following microphotographs of the front glass plate that contains color filters demonstrate the pixels lighting up:

The following microphotographs (all taken in combined transmitted and reflected light for extra contrast) of the back glass plate show the circuitry driving the liquid crystals confined between the two glass plates.

First, row (gate) drivers. There’s 128 in total. Note the numbered LCD rows.

Second, column (source) drivers. There’s 384 in total, so the routing is far more dense. Note that the column drivers are located at the side of the display far from the controller, likely because of lack of space. Note the thick power distribution traces.

At last, here’s a magnified shot of one of the cracks in the glass that killed the LCD:

The cleanest pictures were taken by wetting a cotton bud with IPA, then swabbing the glass with the cotton bud such as to leave a thin film but also remove all junk somewhere out of the visual field, and photographing while the field has not evaporated. IPA appears to be nearly index-matched with the glass used in this LCD, and so it hides most if not all imperfections in the glass, apart from any cleaning that may happen as a result of this procedure.

Nokia 3220 transflective LCD microphotography

2018-08-02T01:56:23Z

I took some microphotographs of a Nokia 3220 (RH-37) transflective LCD using an Amscope ME300TZ-2L-3M metallurgical microscope. These microphotographs were taken on an intact LCD, i.e. transmitted light images were acquired by shining a flashlight through the entire LCD stackup (the built-in diascopic light source is not powerful enough); the 90° reflected light images were acquired using the built-in episcopic light sources, and the 45° reflected light images were acquired using a similar flashlight.

Sony Xperia Z2 LCD microphotography

2018-08-02T00:33:42Z

I took some microphotographs of a counterfeit Sony Xperia Z2 LCD display, bought on Taobao circa 2017, using an Amscope ME300TZ-2L-3M metallurgical microscope. (This display would not initialize with an unmodified firmware, and was factory-programmed to match the never used, due to a bug, DeviceTree display configuration present in the Xperia Z2 kernel image.)

The combined light photo is not digitally manipulated; this is just how it looks with both episcopic and diascopic light sources on.

Replacing the mirror on an Amscope ME300TZ

2018-08-02T00:23:21Z

I have an Amscope ME300TZ-2L-3M metallurgical microscope. While investigating possible causes for poor picture quality and cleaning the optics, I discovered that the mirror was not appropriately fixed to its mount and, in fact, fell off. I glued it back with cyanoacrylate.

After that, I’ve realized that I have a box with a disassembled Pentax *ist DS2 camera, so I’ve removed the mirror from the mirror assembly, heated it at approx. 180 °C to soften the rubber (apparently silicone) glue attaching it to the mirror mount, scraped off the glue with a fingernail, and attached it to the microscope mirror mount. For that I had to, first, remove the original mirror using a heat gun at approx. 280 °C, which made the cyanoacrylate viscoelastic but (predictably) broke the mirror in the process, and second, file down one part of the mirror mount, as while the Pentax mirror is nearly identical in dimensions to the original mirror, it is slightly wider and slightly shorter.

The new mirror performs slightly better than the old one, with a small but noticeable reduction in glare, likely due to the different coating. The overall function of the microscope is not significantly affected.