Skip to content

Commit e02fbb6

Browse files
z4p5a9tim-smart
andauthored
Fix Semaphore.withPermits leaking permits when interrupted (#6910)
Co-authored-by: Tim Smart <[email protected]>
1 parent 0b4a3c4 commit e02fbb6

3 files changed

Lines changed: 174 additions & 41 deletions

File tree

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"effect": patch
3+
---
4+
5+
Fix `Semaphore.withPermits` leaking permits when interrupted between acquiring them and installing their release.

‎packages/effect/src/Semaphore.ts‎

Lines changed: 46 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -204,6 +204,24 @@ export interface Semaphore {
204204
*/
205205
export const makeUnsafe = (permits: number): Semaphore => new SemaphoreImpl(permits)
206206

207+
const waitForPermits = <A, E, R>(
208+
self: SemaphoreImpl,
209+
n: number,
210+
effect: Effect.Effect<A, E, R>
211+
): Effect.Effect<A, E, R> =>
212+
internal.callback((resume) => {
213+
if (self.free >= n) return resume(effect)
214+
const observer = () => {
215+
if (self.free < n) return
216+
self.waiters.delete(observer)
217+
resume(effect)
218+
}
219+
self.waiters.add(observer)
220+
return internal.sync(() => {
221+
self.waiters.delete(observer)
222+
})
223+
})
224+
207225
class SemaphoreImpl implements Semaphore {
208226
public waiters = new Set<() => void>()
209227
public taken = 0
@@ -220,18 +238,7 @@ class SemaphoreImpl implements Semaphore {
220238
take(n: number): Effect.Effect<number> {
221239
const take: Effect.Effect<number> = internal.suspend(() => {
222240
if (this.free < n) {
223-
return internal.callback((resume) => {
224-
if (this.free >= n) return resume(take)
225-
const observer = () => {
226-
if (this.free < n) return
227-
this.waiters.delete(observer)
228-
resume(take)
229-
}
230-
this.waiters.add(observer)
231-
return internal.sync(() => {
232-
this.waiters.delete(observer)
233-
})
234-
})
241+
return waitForPermits(this, n, take)
235242
}
236243
this.taken += n
237244
return internal.succeed(n)
@@ -247,58 +254,56 @@ class SemaphoreImpl implements Semaphore {
247254
})
248255
}
249256

250-
updateTakenUnsafe(fiber: Fiber<any, any>, f: (n: number) => number): number {
251-
this.taken = f(this.taken)
257+
releaseUnsafe(fiber: Fiber<any, any>, n: number): number {
258+
this.taken -= n
252259
if (this.waiters.size > 0) {
253260
fiber.currentDispatcher.scheduleTask(() => {
254-
const iter = this.waiters.values()
255-
let item = iter.next()
256-
while (item.done === false && this.free > 0) {
257-
item.value()
258-
item = iter.next()
261+
for (const observer of this.waiters) {
262+
if (this.free <= 0) break
263+
observer()
259264
}
260265
}, 0)
261266
}
262267
return this.free
263268
}
264269

265-
updateTaken(f: (n: number) => number): Effect.Effect<number> {
266-
return core.withFiber((fiber) => internal.succeed(this.updateTakenUnsafe(fiber, f)))
267-
}
268-
269270
resize(permits: number) {
270271
return core.withFiber((fiber) => {
271272
this.permits = permits
272273
if (this.free < 0) return internal.void
273-
this.updateTakenUnsafe(fiber, (taken) => taken)
274+
this.releaseUnsafe(fiber, 0)
274275
return internal.void
275276
})
276277
}
277278

278279
release(n: number): Effect.Effect<number> {
279-
return this.updateTaken((taken) => taken - n)
280+
return core.withFiber((fiber) => internal.succeed(this.releaseUnsafe(fiber, n)))
280281
}
281282

282283
get releaseAll(): Effect.Effect<number> {
283-
return this.updateTaken((_) => 0)
284+
return core.withFiber((fiber) => internal.succeed(this.releaseUnsafe(fiber, this.taken)))
284285
}
285286

286287
withPermits(n: number) {
287288
return <A, E, R>(self: Effect.Effect<A, E, R>) =>
288-
internal.uninterruptibleMask((restore) =>
289-
internal.flatMap(
290-
restore(this.take(n)),
291-
(permits) =>
292-
internal.onExitPrimitive(
293-
restore(self),
294-
() => {
295-
this.updateTakenUnsafe(internal.getCurrentFiber()!, (taken) => taken - permits)
296-
return undefined
297-
},
298-
true
299-
)
300-
)
301-
)
289+
internal.uninterruptibleMask((restore) => {
290+
const acquire: Effect.Effect<A, E, R> = internal.suspend(() => {
291+
if (this.free < n) {
292+
const wait = waitForPermits(this, n, internal.void)
293+
return internal.flatMap(restore(wait), () => acquire)
294+
}
295+
this.taken += n
296+
return internal.onExitPrimitive(
297+
restore(self),
298+
() => {
299+
this.releaseUnsafe(internal.getCurrentFiber()!, n)
300+
return undefined
301+
},
302+
true
303+
)
304+
})
305+
return acquire
306+
})
302307
}
303308

304309
readonly withPermit = this.withPermits(1)
@@ -309,7 +314,7 @@ class SemaphoreImpl implements Semaphore {
309314
if (this.free < n) return internal.succeedNone
310315
this.taken += n
311316
return internal.onExitPrimitive(restore(internal.asSome(self)), () => {
312-
this.updateTakenUnsafe(internal.getCurrentFiber()!, (taken) => taken - n)
317+
this.releaseUnsafe(internal.getCurrentFiber()!, n)
313318
return undefined
314319
}, true)
315320
})

‎packages/effect/test/Semaphore.test.ts‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -332,6 +332,129 @@ describe("Semaphore", () => {
332332
assert.isTrue(acquired)
333333
}))
334334

335+
it.effect("withPermits interrupted at any operation does not leak permits", () =>
336+
Effect.gen(function*() {
337+
let operations = 0
338+
const counted = new Scheduler.MixedScheduler()
339+
const baseline = yield* (yield* Semaphore.make(1)).withPermits(1)(Effect.void).pipe(
340+
Effect.provideService(Scheduler.Scheduler, {
341+
executionMode: counted.executionMode,
342+
makeDispatcher: () => counted.makeDispatcher(),
343+
shouldYield: (fiber) => {
344+
operations++
345+
return counted.shouldYield(fiber)
346+
}
347+
}),
348+
Effect.forkChild
349+
)
350+
yield* Fiber.await(baseline)
351+
352+
const recovered: Array<boolean> = []
353+
let ranUnderPermits = false
354+
355+
for (let at = 1; at <= operations; at++) {
356+
const sem = yield* Semaphore.make(1)
357+
const base = new Scheduler.MixedScheduler()
358+
let seen = 0
359+
const scheduler: Scheduler.Scheduler = {
360+
executionMode: base.executionMode,
361+
makeDispatcher: () => base.makeDispatcher(),
362+
shouldYield: (fiber) => {
363+
if (++seen === at) fiber.interruptUnsafe()
364+
return base.shouldYield(fiber)
365+
}
366+
}
367+
368+
const holder = yield* sem.withPermits(1)(
369+
Effect.sync(() => {
370+
ranUnderPermits = true
371+
})
372+
).pipe(
373+
Effect.provideService(Scheduler.Scheduler, scheduler),
374+
Effect.forkChild
375+
)
376+
yield* Fiber.await(holder)
377+
378+
const result = yield* sem.withPermitsIfAvailable(1)(Effect.void)
379+
recovered.push(Option.isSome(result))
380+
}
381+
382+
assert.deepStrictEqual(recovered, Array.from({ length: operations }, () => true))
383+
assert.isTrue(ranUnderPermits)
384+
}))
385+
386+
it.effect("queued withPermits interrupted at any operation does not leak permits", () =>
387+
Effect.gen(function*() {
388+
const queuedScheduler = (
389+
tasks: Array<() => void>,
390+
onOperation: (fiber: Fiber.Fiber<unknown, unknown>) => void
391+
) => {
392+
const scheduler: Scheduler.Scheduler = {
393+
executionMode: "async",
394+
makeDispatcher: () => ({
395+
scheduleTask(task) {
396+
tasks.push(task)
397+
},
398+
flush() {}
399+
}),
400+
shouldYield: (fiber) => {
401+
onOperation(fiber)
402+
return false
403+
}
404+
}
405+
return scheduler
406+
}
407+
408+
let operations = 0
409+
const baselineSem = yield* Semaphore.make(1)
410+
const baselineTasks: Array<() => void> = []
411+
const baselineHolder = yield* Effect.forkChild(baselineSem.withPermits(1)(Effect.never))
412+
yield* Effect.yieldNow
413+
yield* Effect.forkChild(
414+
baselineSem.withPermits(1)(Effect.void).pipe(
415+
Effect.provideService(Scheduler.Scheduler, queuedScheduler(baselineTasks, () => operations++))
416+
),
417+
{ startImmediately: true }
418+
)
419+
yield* Fiber.interrupt(baselineHolder)
420+
yield* Effect.yieldNow
421+
while (baselineTasks.length > 0) baselineTasks.shift()!()
422+
423+
const recovered: Array<boolean> = []
424+
let ranUnderPermits = false
425+
426+
for (let at = 1; at <= operations; at++) {
427+
const sem = yield* Semaphore.make(1)
428+
const tasks: Array<() => void> = []
429+
let seen = 0
430+
const scheduler = queuedScheduler(tasks, (fiber) => {
431+
if (++seen === at) fiber.interruptUnsafe()
432+
})
433+
434+
const holder = yield* Effect.forkChild(sem.withPermits(1)(Effect.never))
435+
yield* Effect.yieldNow
436+
437+
yield* Effect.forkChild(
438+
sem.withPermits(1)(
439+
Effect.sync(() => {
440+
ranUnderPermits = true
441+
})
442+
).pipe(Effect.provideService(Scheduler.Scheduler, scheduler)),
443+
{ startImmediately: true }
444+
)
445+
446+
yield* Fiber.interrupt(holder)
447+
yield* Effect.yieldNow
448+
while (tasks.length > 0) tasks.shift()!()
449+
450+
const result = yield* sem.withPermitsIfAvailable(1)(Effect.void)
451+
recovered.push(Option.isSome(result))
452+
}
453+
454+
assert.deepStrictEqual(recovered, Array.from({ length: operations }, () => true))
455+
assert.isTrue(ranUnderPermits)
456+
}))
457+
335458
it.effect("takeIfAvailable acquires permits when they are available", () =>
336459
Effect.gen(function*() {
337460
const sem = yield* Semaphore.make(2)

0 commit comments

Comments
 (0)