Outcurses

(11 intermediate revisions by the same user not shown)

Line 1:

[[File:OUTCURSES.png|right|thumb|bling up that terminal]]

During the development of [[Growlight]] and [[Omphalos]], I found myself implementing significant UI code atop [[ncurses]]. It's my goal to extract most of this, unify it, and make it available as liboutcurses. Code lives on [https://github.com/dankamongmen/~~outcurses~~ github].

During the development of [[Growlight]] and [[Omphalos]], I found myself implementing significant UI code atop [[ncurses]]. It's my goal to extract most of this, unify it, and make it available as liboutcurses. Code lives on [https://github.com/dankamongmen/panelreels github].

Why is it called 'outcurses'? Because there's [https://www.collinsdictionary.com/us/dictionary/english/outcurse more cursing], duh.

This project led to [[notcurses]].

==Palette fades==

Line 8:

Line 10:

==Metric suffixes==

Not ncurses-related, but it's UI, so I stuck it here. Fed a <tt>uintmax_t</tt> (large enough to represent any unsigned integer type), a buffer, and a base (almost always 1000 or 1024), <tt>enmetric</tt> renders the number into the buffer such that the characteristic (material to the left of the decimal point) is less than the base. For numbers greater than the base, this means some metric suffix will be employed, and that the displayed number will have a mantissa (e.g. 1234 with a base of 1000 becomes 1.234K). Numbers through 2^89 are properly handled, using the suffixes Y, Z, E, P, T, G, M, and K. Use of base 1024 is necessary to properly employ the [https://en.wikipedia.org/wiki/Kibibyte metric units of digital information]. For instance, a "10 terabyte" hard drive typically has 10* 1012 == 10,000,000,000,000 (ten trillion) bytes aka 10TB, but 10 * 240 == 10 * 1024 * 1024 * 1024 * 1024 is 10,995,116,277,760 bytes aka 10 tibibytes aka 10TiB. A kilobyte is 97.7% of a kibibyte, but a terabyte is only 91% of a tibibyte.

Not ncurses-related, but it's UI, so I stuck it here. Fed a <tt>uintmax_t</tt> (large enough to represent any unsigned integer type), a buffer, and a base (almost always 1000 or 1024), <tt>enmetric</tt> renders the number into the buffer such that the characteristic (material to the left of the decimal point) is less than the base. For numbers greater than the base, this means some metric suffix will be employed, and that the displayed number will have a mantissa (e.g. 1234 with a base of 1000 becomes 1.234K). Numbers through 2^89 are properly handled, using the suffixes Y, Z, E, P, T, G, M, and K. Use of base 1024 is necessary to properly employ the [https://en.wikipedia.org/wiki/Kibibyte metric units of digital information]. For instance, a 10 terabyte hard drive typically has 10* 1012 == 10,000,000,000,000 (ten trillion) bytes aka 10TB, but 10 * 240 == 10 * 1024 * 1024 * 1024 * 1024 is 10,995,116,277,760 bytes aka 10 tibibytes aka 10TiB. A kilobyte is 97.7% of a kibibyte, but a terabyte is only 91% of a tibibyte.

Three characters of mantissa are used for characteristics less than 10; two characters are used for characteristics greater than 9 but less than 100; one character is used for characteristics greater than 99. Note that the most precision is available for the smallest characteristics, which is desirable, since the mantissa represents a greater portion of the total in these cases.

Line 241:

Line 243:

Growlight resolved this by requiring ncurses events to take the core lock before taking the ncurses lock. This requires cooperation from the core and a simplistic locking scheme, and serializes most of the program against the UI, but does resolve the problem. Omphalos appears not to lock the core from within the UI. Instead, the UI carries around significant copied data—enough to establish the number of lines an interface can require at any given time, though not enough to redraw the interface details. At some point, the omphalos UI takes a deep breath and dereferences a pointer into unlocked application-side data. This can be made to work only if the UI copies all metadata necessary for structuring the output, AND can rely on the core neither moving nor deleting

data to which the UI points without taking the UI lock. In omphalos, for instance, receipt of an <tt>RTM_DELLINK</tt> [[netlink]] message indicating that an interface has been deleted is handled thus:

data to which the UI points without taking the UI lock. In omphalos, for instance, receipt of an <tt>RTM_DELLINK</tt> [[netlink]] message indicating that an interface has been deleted is handled thus (all in the context of the thread receiving the netlink event):

<ul>

<li>processing the <tt>RTM_DELLINK</tt> to extract the interface index</li>

<li>acquiring the core lock</li>

<li>acquiring the core's iface lock</li>

<li>finding the interface specified by this index</li>

<li>finding the <tt>interface</tt> specified by this index</li>

<li>removing the interface from the lookup structure</li>

<li>removing the <tt>interface</tt> from the lookup structure</li>

<li>acquiring the UI lock (~~via~~ <tt>interface_removed_callback</tt>)</li>

<li>acquiring the <tt>interface</tt>'s marshal lock</li>

<li>removing the <tt>iface_state</tt> from its circular list of all ~~ifaces~~</li>

<li>cancelling the packet socket thread for this <tt>interface</tt></li>

<li>removing the <tt>reelbox</tt> from its own circular list of visible ~~ifaces~~</li>

<li>releasing the <tt>interface</tt>'s marshal lock</li>

<li>joining the packet socket thread for this <tt>interface</tt></li>

<li>acquiring the UI lock (start of <tt>interface_removed_callback</tt>)</li>

<li>removing the <tt>iface_state</tt> from its circular list of all <tt>iface_state</tt>s</li>

<li>removing the <tt>reelbox</tt> from its own circular list of visible <tt>reelbox</tt>en</li>

<li>destroying the panel, reelbox, and iface_state</li>

<li>repairing the screen by filling in this hole, possibly making other ifaces visible</li>

<li>releasing the UI lock</li>

<li>destroying the interface</li>

<li>releasing the core's iface lock</li>

<li>destroying the <tt>interface</tt></li>

</ul>

Not only is this a tremendous amount of (possibly blocking!) work done while holding *multiple* locks, but it is complicated for the application programmer (what goes away when?), difficult to reason about what needs to be copied into the UI's state (and this process does not self-recover if the two ever diverge), ~~wastes~~ memory and time with said copies

Not only is this a tremendous amount of (possibly blocking!) work done while holding *multiple* locks, but it is complicated for the application programmer (what goes away when?), it is difficult to reason about what needs to be copied into the UI's state (and this process does not self-recover if the two ever diverge), and we waste memory and time with said copies. That marshaling lock could probably be reduced to an atomic, as it's unattached to a condvar. Can we not unlock the iface lock after splicing out the interface from its lookup structure? It would seem so, but verifying it would be more effort than I want to put in at the moment. Finally, I suspect it all to be broken. Who knows. This sucks, and I ought set myself on fire.

For Outcurses and its general-purpose panelreels, we cannot assume deep application assistance. We cannot assume understanding of application internals. We cannot assume that it is possible to cache structure beyond the circular list of top-level objects corresponding to tablets, and we cannot even assume this last to be truly reflected in the application, which might very well not have a concept of ordering among the tablets. Furthermore, it would be a fine thing indeed to wholly decouple screen updates from any locked core code.

Accomplishing this last eliminates almost all of our problems, while introducing a few new ones. Decoupling screen updates from core updates means that UI code cannot be called from any application context holding core locks. This immediately suggests a producer/consumer model where updates are written to a shared, synchronized buffer. In a model where data is copied to the UI state (and thus it needn't lock against the core), these updates might take the form of piecemeal instructions ("iface 2 has added a subelement. iface 3 has received the following packet." etc.), and it would be necessary to process the updates in-order and cumulatively, though actual screen redrawing could be postponed to the end of a batch of updates. Alternatively, the entirety of state could be copied for each update, eliminating complexity in both the UI and core for a price paid in memory and time. Finally, nothing could be published save "iface 2 has changed", requiring a locked call into the core to get the data (and reference counters for data which might be destroyed). Comparing these strategies, we see:

{| class="wikitable"

|+ Deadlock-resistant core update strategies

|-

! Method !! Locked call into core !! Unnecessary copies !! Limits on core structure !! UI complexity

|-

| Piecemeal updates || No || Small || Yes || Large

|-

| Snapshots || No || Large || No || None

|-

| Notifications || Yes || None || No || Small

|-

|}

</center>

This would seem strong support for snapshots. The size would theoretically be unbounded (i.e. copy output of the object assuming an infinite tablet), but it seems we could bind it to the total size of the screen. This runs into some details that seem possible to overcome (what if a new, larger display is attached to the machine during runtime, and the window is moved to that screen, and maximized?). The fatal problem in my mind is that these non-trivial (if bounded) copies must be performed for all interfaces, whether on-screen or off-. So far as I can tell, any scheme which avoids copies for off-screen tablets requires a locked callback into the core, since a UI event can bring a tablet on-screen independently of any core event. Since there is an unbounded number of off-screen interfaces needing copies, the overall copying can once more be unbounded, and thus the snapshot approach is unacceptable. Notifications it is, then.

The problem with notifications is primarily that objects can be removed by the core while the UI still holds references to them. The UI blindly invoking these objects will result in catastrophe. We can add a reference count to the objects, at the cost of some application complexity (the application must down the reference counter, and provide a destructor that can be called from UI context). Avoiding this complexity in the application seems to require substantial complexity in outcurses: the application can be allowed to freely destroy its object following posting notification of the deletion if outcurses takes this into consideration when performing other actions. For instance, prior to user keypress selecting the previous tablet, it must be verified that this tablet still exists. If the move pushes some other tablet partially off-screen, it must be verified that this other tablet still exists prior to redrawing it, etc. In the case where the tablet no longer exists, action must be taken to remove it (and fill the void) along all manner of new control flow paths. Alternatively, the callback could require a core lookup each time.

==Panel animations==

Line 266:

Line 296:

* The Python [https://docs.python.org/2/library/curses.panel.html curses.panel] module

* My [[Xcurses]] project, which went exactly nowhere

* [http://www.leonerd.org.uk/code/libtickit/ libtickit]

[[CATEGORY: Projects]]

[[CATEGORY: Terminals]]

Outcurses: Difference between revisions

Dank (talk | contribs)

@@ Line 1: / Line 1: @@
 [[File:OUTCURSES.png|right|thumb|bling up that terminal]]
-During the development of [[Growlight]] and [[Omphalos]], I found myself implementing significant UI code atop [[ncurses]]. It's my goal to extract most of this, unify it, and make it available as liboutcurses. Code lives on [https://github.com/dankamongmen/outcurses github].
+During the development of [[Growlight]] and [[Omphalos]], I found myself implementing significant UI code atop [[ncurses]]. It's my goal to extract most of this, unify it, and make it available as liboutcurses. Code lives on [https://github.com/dankamongmen/panelreels github].
 Why is it called 'outcurses'? Because there's [https://www.collinsdictionary.com/us/dictionary/english/outcurse more cursing], duh.
+This project led to [[notcurses]].
 ==Palette fades==
@@ Line 8: / Line 10: @@
 ==Metric suffixes==
-Not ncurses-related, but it's UI, so I stuck it here. Fed a <tt>uintmax_t</tt> (large enough to represent any unsigned integer type), a buffer, and a base (almost always 1000 or 1024), <tt>enmetric</tt> renders the number into the buffer such that the characteristic (material to the left of the decimal point) is less than the base. For numbers greater than the base, this means some metric suffix will be employed, and that the displayed number will have a mantissa (e.g. 1234 with a base of 1000 becomes 1.234K). Numbers through 2^89 are properly handled, using the suffixes Y, Z, E, P, T, G, M, and K. Use of base 1024 is necessary to properly employ the [https://en.wikipedia.org/wiki/Kibibyte metric units of digital information]. For instance, a "10 terabyte" hard drive typically has 10* 10<sup>12</sup> == 10,000,000,000,000 (ten trillion) bytes aka 10TB, but 10 * 2<sup>40</sup> == 10 * 1024 * 1024 * 1024 * 1024 is 10,995,116,277,760 bytes aka 10 tibibytes aka 10TiB. A kilobyte is 97.7% of a kibibyte, but a terabyte is only 91% of a tibibyte.
+Not ncurses-related, but it's UI, so I stuck it here. Fed a <tt>uintmax_t</tt> (large enough to represent any unsigned integer type), a buffer, and a base (almost always 1000 or 1024), <tt>enmetric</tt> renders the number into the buffer such that the characteristic (material to the left of the decimal point) is less than the base. For numbers greater than the base, this means some metric suffix will be employed, and that the displayed number will have a mantissa (e.g. 1234 with a base of 1000 becomes 1.234K). Numbers through 2^89 are properly handled, using the suffixes Y, Z, E, P, T, G, M, and K. Use of base 1024 is necessary to properly employ the [https://en.wikipedia.org/wiki/Kibibyte metric units of digital information]. For instance, a 10 terabyte hard drive typically has 10* 10<sup>12</sup> == 10,000,000,000,000 (ten trillion) bytes aka 10TB, but 10 * 2<sup>40</sup> == 10 * 1024 * 1024 * 1024 * 1024 is 10,995,116,277,760 bytes aka 10 tibibytes aka 10TiB. A kilobyte is 97.7% of a kibibyte, but a terabyte is only 91% of a tibibyte.
 Three characters of mantissa are used for characteristics less than 10; two characters are used for characteristics greater than 9 but less than 100; one character is used for characteristics greater than 99. Note that the most precision is available for the smallest characteristics, which is desirable, since the mantissa represents a greater portion of the total in these cases.
@@ Line 241: / Line 243: @@
 Growlight resolved this by requiring ncurses events to take the core lock before taking the ncurses lock. This requires cooperation from the core and a simplistic locking scheme, and serializes most of the program against the UI, but does resolve the problem. Omphalos appears not to lock the core from within the UI. Instead, the UI carries around significant copied data—enough to establish the number of lines an interface can require at any given time, though not enough to redraw the interface details. At some point, the omphalos UI takes a deep breath and dereferences a pointer into unlocked application-side data. This can be made to work only if the UI copies all metadata necessary for structuring the output, AND can rely on the core neither moving nor deleting
-data to which the UI points without taking the UI lock. In omphalos, for instance, receipt of an <tt>RTM_DELLINK</tt> [[netlink]] message indicating that an interface has been deleted is handled thus:
+data to which the UI points without taking the UI lock. In omphalos, for instance, receipt of an <tt>RTM_DELLINK</tt> [[netlink]] message indicating that an interface has been deleted is handled thus (all in the context of the thread receiving the netlink event):
 <ul>
 <li>processing the <tt>RTM_DELLINK</tt> to extract the interface index</li>
-<li>acquiring the core lock</li>
+<li>acquiring the core's iface lock</li>
-<li>finding the interface specified by this index</li>
+<li>finding the <tt>interface</tt> specified by this index</li>
-<li>removing the interface from the lookup structure</li>
+<li>removing the <tt>interface</tt> from the lookup structure</li>
-<li>acquiring the UI lock (via <tt>interface_removed_callback</tt>)</li>
+<li>acquiring the <tt>interface</tt>'s marshal lock</li>
-<li>removing the <tt>iface_state</tt> from its circular list of all ifaces</li>
+<li>cancelling the packet socket thread for this <tt>interface</tt></li>
-<li>removing the <tt>reelbox</tt> from its own circular list of visible ifaces</li>
+<li>releasing the <tt>interface</tt>'s marshal lock</li>
+<li>joining the packet socket thread for this <tt>interface</tt></li>
+<li>acquiring the UI lock (start of <tt>interface_removed_callback</tt>)</li>
+<li>removing the <tt>iface_state</tt> from its circular list of all <tt>iface_state</tt>s</li>
+<li>removing the <tt>reelbox</tt> from its own circular list of visible <tt>reelbox</tt>en</li>
 <li>destroying the panel, reelbox, and iface_state</li>
 <li>repairing the screen by filling in this hole, possibly making other ifaces visible</li>
 <li>releasing the UI lock</li>
-<li>destroying the interface</li>
+<li>releasing the core's iface lock</li>
+<li>destroying the <tt>interface</tt></li>
 </ul>
-Not only is this a tremendous amount of (possibly blocking!) work done while holding *multiple* locks, but it is complicated for the application programmer (what goes away when?), difficult to reason about what needs to be copied into the UI's state (and this process does not self-recover if the two ever diverge), wastes memory and time with said copies
+Not only is this a tremendous amount of (possibly blocking!) work done while holding *multiple* locks, but it is complicated for the application programmer (what goes away when?), it is difficult to reason about what needs to be copied into the UI's state (and this process does not self-recover if the two ever diverge), and we waste memory and time with said copies. That marshaling lock could probably be reduced to an atomic, as it's unattached to a condvar. Can we not unlock the iface lock after splicing out the interface from its lookup structure? It would seem so, but verifying it would be more effort than I want to put in at the moment. Finally, I suspect it all to be broken. Who knows. This sucks, and I ought set myself on fire.
+For Outcurses and its general-purpose panelreels, we cannot assume deep application assistance. We cannot assume understanding of application internals. We cannot assume that it is possible to cache structure beyond the circular list of top-level objects corresponding to tablets, and we cannot even assume this last to be truly reflected in the application, which might very well not have a concept of ordering among the tablets. Furthermore, it would be a fine thing indeed to wholly decouple screen updates from any locked core code.
+Accomplishing this last eliminates almost all of our problems, while introducing a few new ones. Decoupling screen updates from core updates means that UI code cannot be called from any application context holding core locks. This immediately suggests a producer/consumer model where updates are written to a shared, synchronized buffer. In a model where data is copied to the UI state (and thus it needn't lock against the core), these updates might take the form of piecemeal instructions ("iface 2 has added a subelement. iface 3 has received the following packet." etc.), and it would be necessary to process the updates in-order and cumulatively, though actual screen redrawing could be postponed to the end of a batch of updates. Alternatively, the entirety of state could be copied for each update, eliminating complexity in both the UI and core for a price paid in memory and time. Finally, nothing could be published save "iface 2 has changed", requiring a locked call into the core to get the data (and reference counters for data which might be destroyed). Comparing these strategies, we see:
+<center>
+{| class="wikitable"
+|+ Deadlock-resistant core update strategies
+|-
+! Method !! Locked call into core !! Unnecessary copies !! Limits on core structure !! UI complexity
+|-
+| Piecemeal updates || No || Small || Yes || Large
+|-
+| Snapshots || No || Large || No || None
+|-
+| Notifications || Yes || None || No || Small
+|-
+|}
+</center>
+This would seem strong support for snapshots. The size would theoretically be unbounded (i.e. copy output of the object assuming an infinite tablet), but it seems we could bind it to the total size of the screen. This runs into some details that seem possible to overcome (what if a new, larger display is attached to the machine during runtime, and the window is moved to that screen, and maximized?). The fatal problem in my mind is that these non-trivial (if bounded) copies must be performed for all interfaces, whether on-screen or off-. So far as I can tell, any scheme which avoids copies for off-screen tablets requires a locked callback into the core, since a UI event can bring a tablet on-screen independently of any core event. Since there is an unbounded number of off-screen interfaces needing copies, the overall copying can once more be unbounded, and thus the snapshot approach is unacceptable. Notifications it is, then.
+The problem with notifications is primarily that objects can be removed by the core while the UI still holds references to them. The UI blindly invoking these objects will result in catastrophe. We can add a reference count to the objects, at the cost of some application complexity (the application must down the reference counter, and provide a destructor that can be called from UI context). Avoiding this complexity in the application seems to require substantial complexity in outcurses: the application can be allowed to freely destroy its object following posting notification of the deletion if outcurses takes this into consideration when performing other actions. For instance, prior to user keypress selecting the previous tablet, it must be verified that this tablet still exists. If the move pushes some other tablet partially off-screen, it must be verified that this other tablet still exists prior to redrawing it, etc. In the case where the tablet no longer exists, action must be taken to remove it (and fill the void) along all manner of new control flow paths. Alternatively, the callback could require a core lookup each time.
 ==Panel animations==
@@ Line 266: / Line 296: @@
 * The Python [https://docs.python.org/2/library/curses.panel.html curses.panel] module
 * My [[Xcurses]] project, which went exactly nowhere
+* [http://www.leonerd.org.uk/code/libtickit/ libtickit]
 [[CATEGORY: Projects]]
+[[CATEGORY: Terminals]]