Changes in / [79ba50c:5e0b6657]


Ignore:
Location:
doc/theses/mike_brooks_MMath
Files:
1 deleted
8 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/background.tex

    r79ba50c r5e0b6657  
    77
    88C reports many ill-typed expressions as warnings.
    9 For example, these attempts to assign @y@ to @x@ and vice-versa are ill-typed.
     9For example, these attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed.
    1010\lstinput{12-15}{bkgd-c-tyerr.c}
    1111with warnings:
    … …  
    2121note: expected 'void (*)(void)' but argument is of type 'float *'
    2222\end{cfa}
     23with a segmentation fault at runtime.
    2324Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
    2425Compiling with flag @-Werror@, which turns warnings into errors, is often too pervasive, because some warnings are just warnings, \eg an unused variable.
    … …  
    8687(\VRef{s:ArraysDecay} shows pointer decay allows the first form to be written @pa[i] += 1@, which is further syntax confusion.)
    8788Again, if the priorities were reversed, the expressions become more intuitive: @*pa[i] += 1@ and @*(ap[i]) += 1@.
    88 Note, a similar priority inversion exists between deference '@*@' and field selection '@.@' (period), so @*ps.f@ means @*(ps.f)@;
     89Note, a similar priority inversion exists between deference @*@ and field selection @.@ (period), so @*ps.f@ means @*(ps.f)@;
    8990this anomaly is \emph{fixed} with operator @->@, which performs the two operations in the more intuitive order: @sp->f@ $\Rightarrow$ @(*sp).f@.
    9091\end{itemize}
    … …  
    127128As declaration size increases, it becomes corresponding difficult to read and understand the C form, whereas reading and understanding a \CFA declaration has linear complexity.
    128129Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations, \eg \CC \lstinline[language=C++]{auto f( int ) -> int}.
    129 However, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.
     130(Note, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.)
    130131Interestingly, programmers normally speak a declaration from left to right, regardless of how it is written.
    131132(It is unclear if Hebrew or Arabic speakers, say declarations right to left.)
    132133
    133 Specifically, \VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef[Chapter]{c:Array}.
     134\VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef[Chapter]{c:Array}.
    134135The \CFA-thesis column shows the new array declaration form, which is my contribution to safety and ergonomics.
    135136The table shows there are multiple yet equivalent forms for the array types under discussion, and subsequent discussion shows interactions with orthogonal (but easily confused) language features.
    … …  
    137138The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
    138139Removing the declared variable @x@, gives the type used for variable, structure field, cast, or error messages.
    139 Unfortunately, parameter declarations have more syntactic forms and rules \see{Section~\ref{s:ArraysDecay}~\VPageref{p:ParameterDeclarations}}.
     140Unfortunately, parameter declarations have more syntactic forms and rules.
    140141
    141142\begin{table}
    … …  
    143144\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
    144145\label{bkgd:ar:usr:avp}
    145 \setlength{\tabcolsep}{12pt}
    146 \begin{tabular}{@{}ll|l|l|l@{}}
     146\begin{tabular}{ll|l|l|l}
    147147        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
    148148        \hline
    … …  
    253253Using the type form yields the same results as the prior expression form.
    254254\lstinput{46-49}{bkgd-carray-arrty.c}
    255 The results are also the same when there is no allocation at all, \eg a parameter declaration.
     255The results are also the same when there is no allocation at all.
    256256This time, starting from a pointer-to-array type:
    257257\lstinput{51-57}{bkgd-carray-arrty.c}
    … …  
    297297``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
    298298\end{quote}
    299 This phenomenon is the famous (infamous) \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
     299This phenomenon is the famous \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
    300300It is worthy to note that the list of exceptional cases does not feature the occurrence of @ar@ in @ar[i]@.
    301301Thus, subscripting happens on pointers not arrays.
    … …  
    305305\cite[\S~6.5.6.8]{C11} explains that the addition, of a pointer with an integer type, is defined only when the pointer refers to an element that is in an array, with a meaning of @i@ elements away from, which is valid if @ar@ is big enough and @i@ is small enough.
    306306Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
    307 Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing, as plus is commutative.
     307Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
    308308
    309309Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
    … …  
    318318But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.
    319319
    320 Under this assumption, a pointer, @p@, being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around @p@'s address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p).t@.
    321 I call this phenomenon \emph{array diffraction}, which is a diffraction of a single-element pointer into the assumption that its target is conceptually in the middle of an array whose size is unlimited in both directions.
     320Under this assumption, a pointer being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p)@.
     321I call this phenomenon \emph{array diffraction}, which is a diffraction of a single-element pointer into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
    322322No pointer is exempt from array diffraction.
    323323No array shows its elements without pointer decay.
    324324
    325 \label{p:ParameterDeclarations}
    326325A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
    327326\cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
    … …  
    380379\label{bkgd:ar:usr:decay-parm}
    381380\centering
    382 \setlength{\tabcolsep}{10pt}
    383 \begin{tabular}{@{}llllll@{}}
     381\begin{tabular}{llllll}
    384382        & Description & Type & Parameter Declaration & \CFA  \\
    385383        \hline
    … …  
    428426Unfortunately, there is significant misinformation about VLAs, \eg the stack size is limited (small), or VLAs cause stack failures or are inefficient.
    429427VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.
    430 Most shells limit the maximum stack size to guard against infinite recursion, but the stack size can be set to unlimited, just like the heap.
    431428For types with a dynamic-fixed stack, \eg coroutines or user-level threads, large VLAs can overflow the stack without appropriately sizing the stack, so heap allocation is used when the array size is unbounded.
    432429
    … …  
    439436When working with arrays, \eg linear algebra, array dimensions are referred to as \emph{rows} and \emph{columns} for a matrix, adding \emph{planes} for a cube.
    440437(There is little terminology for higher dimensional arrays.)
    441 For example, an acrostic poem\footnote{A kind of poetry where the first, last or other letters in a line spell out a word or phrase in a vertical column.}
     438For example, an acrostic poem\footnote{A type of poetry where the first, last or other letters in a line spell out a particular word or phrase in a vertical column.}
    442439can be treated as a grid of characters, where the rows are the text and the columns are the embedded keyword(s).
    443440Within a poem, there is the concept of a \newterm{slice}, \eg a row is a slice for the poem text, a column is a slice for a keyword.
    … …  
    513510For example, an array-of-array may be an array of row pointers to arrays of columns, so the rows may not be contiguous in memory nor even the same length (triangular matrix).
    514511Regardless, there is usually a uniform subscripting syntax masking the memory layout, even though a language could differentiated between the two forms using subscript syntax, \eg @m[1,2]@ \vs @aa[1][2]@.
    515 Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (\eg caching/NUMA effects).
    516 C also provides non-contiguous arrays-of-arrays:
     512Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (caching/NUMA effects).
     513
     514C also provides non-contiguous arrays-of-arrays.
    517515\begin{cfa}
    518516int m[5][5];                                                    $\C{// contiguous}$
    519517int * aa[5];                                                    $\C{// non-contiguous}$
    520518\end{cfa}
    521 both with different memory layout using the same subscripting and different degrees of issues.
    522 
     519both with different memory layout using the same subscripting, and both with different degrees of issues.
    523520The focus of this work is on the contiguous multidimensional arrays in C.
    524521The reason is that programmers are often forced to use the more complex array-of-array form when a contiguous array would be simpler, faster, and safer.
    … …  
    527524\VRef[Figure]{f:ContiguousNon-contiguous} shows a powerful extension made in C99 for manipulating contiguous \vs non-contiguous arrays.\footnote{C90 also supported non-contiguous arrays.}
    528525For contiguous-array arguments (including VLA), C99 conjoins one or more of the parameters as a downstream dimension(s), \eg @cols@, implicitly using this parameter to compute the row stride of @m@.
    529 There is now sufficient information to support array copying and subscript checking along the columns to prevent changing the argument or buffer-overflow problems, \emph{but neither feature is provided}.
     526There is now sufficient information to support array copying and subscript checking along the columns to prevent changing the argument or buffer-overflow problems, but neither feature is provided.
    530527If the declaration of @fc@ is changed to:
    531528\begin{cfa}
    … …  
    535532While this contiguous-array capability is a step forward, it is still the programmer's responsibility to manually manage the number of dimensions and their sizes, both at the function definition and call sites.
    536533That is, the array does not automatically carry its structure and sizes for use in computing subscripts.
    537 While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row with a correctly bounded loop index.
     534While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row correctly with a correctly bounded loop index.
    538535Specifically, there is no requirement that the rows are the same length, like a poem with different length lines.
    539536
    … …  
    586583Again, an array and a point to each of its axes are different.
    587584\lstinput{28-36}{bkgd-carray-mdim.c}
    588 As well, there is pointer decay from each of the matrix axes to pointers, all having the same address.
     585As well, there is pointer decay from each of the matrix axes to pointers, which all have the same address.
    589586\lstinput{38-44}{bkgd-carray-mdim.c}
    590 Finally, subscripting is allowed on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
     587Finally, subscripting on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
    591588
    592589
    … …  
    608605// caller's perspectives of foo and bar
    609606\end{cfa}
    610 From the caller's perspective, the parameter names are semantically optional, but provide useful comments.
    611 From the callee's perspective, parameter names are semantically essential.
     607From the caller's perspective, the parameter names (by virtue of being optional) are (useful) comments;
     608From the callee's perspective, parameter names are semantically significant.
    612609Array parameters introduce a further, subtle, semantic difference and considerable freedom to comment.
    613610
    614 At the semantic level, there is no such thing as an array parameter, except for one case, @T [static 5]@, discussed shortly.
    615 Instead, there are only pointer parameters.
     611At the semantic level, there is no such thing as an array parameter, except for one case (@T [static 5]@) discussed shortly.
     612Rather, there are only pointer parameters.
    616613This fact probably shares considerable responsibility for the common sense of \emph{an array is just a pointer}, which has been refuted in non-parameter contexts.
    617614This fact holds in both the caller's and callee's perspectives.
    618 However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@), which is a pointer type.
    619 This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's and callee's perspectives.
     615However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
     616This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's \vs callee's perspectives.
    620617In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
    621618
    622 C ignores length information given in parameter declarations entirely, when determining a function's type.
    623 For example, it accepts this pair of declarations
    624 \begin{cfa}
    625     void f( int, float[][42] );  $\C{// array of len-42 arrays}$
    626     void f( int n, float[][n]  );   $\C{// array of VLAs}$
    627 \end{cfa}
    628 as a repeat, without an error about conflicting types for @f@.
    629 Yet, entirely different stride calculations would occur in a function body whose parameters were declared in each of the two styles.
     619\PAB{TODO: add examples of mycode/arrr/bugs/c-dependent/x.cfa:v5102,5103,
     620which are shocking how much C ignores.}
    630621
    631622\begin{figure}
    632 \setlength{\tabcolsep}{7pt}
    633623\begin{tabular}{@{}llll@{}}
    634624\begin{cfa}
    … …  
    673663Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
    674664An array parameter declaration can specify the outermost dimension with a dimension value, @[10]@ (which is ignored), an empty dimension list, @[ ]@, or a pointer, @*@, as seen in \VRef[Figure]{f:ArParmEquivDecl}.
    675 The rationale for rejecting the first invalid row follows shortly, while the second invalid row is nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
    676 Note, in the leftmost style, the typechecker ignores the actual value, even for a dynamic expression.
     665The rationale for rejecting the first invalid row follows shortly, while the second invalid row is simple nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
     666Note, in the leftmost style, the typechecker ignores the actual value even in a dynamic expression.
    677667\begin{cfa}
    678668int N;
    … …  
    684674% So are @float[5]*@, @float[]*@ and @float (*)*@.  These latter ones are simply nonsense, though they hint at ``1d array of pointers'', whose equivalent syntax options are, @float *[5]@, @float *[]@, and @float **@.
    685675
    686 It is a matter of taste as to whether a programmer should use the left form to get the most out of commenting subscripting and dimension sizes, sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript'').
     676It is a matter of taste as to whether a programmer should use a form as far left as possible (getting the most out of possible subscripting and dimension sizes), sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript'').
    687677
    688678Note that this equivalence of pointer and array declarations is special to parameters.
    … …  
    690680\begin{cfa}
    691681void f( float * a ) {
    692         float * b = a;          // ok
    693         float c[] = a;          // reject
    694         float d[] = { 1.0, 2.0, 3.0 };  // ok
     682        float * b = a; // ok
     683        float c[] = a; // reject
     684        float d[] = { 1.0, 2.0, 3.0 }; // ok
    695685        static_assert( sizeof(b) == sizeof(float*) );
    696686        static_assert( sizeof(d) != sizeof(float*) );
    697687}
    698688\end{cfa}
    699 The consequence of this equivalence is that the type system does not help a caller get it right.
     689Unfortunately, this equivalence has the consequence that the type system does not help a caller get it right.
    700690\begin{cfa}
    701691float sum( float v[] );
    … …  
    725715void foo( int [static @3@] );
    726716int ar[@10@];
    727 foo( ar );              // check argument dimension 10 > 3
     717foo( ar ); // check argument dimension 10 > 3
    728718\end{cfa}
    729719Here, the @static@ storage qualifier defines the minimum array size for its argument.
    … …  
    738728
    739729With multidimensional arrays, on dimensions after the first, a size is required and, is not ignored.
    740 These sizes (strides) are required for the callee to be able to subscript.
     730These sizes are required for the callee to be able to subscript.
    741731\begin{cfa}
    742732void f( float a[][10], float b[][100] ) {
    … …  
    749739The significance of an inner dimension's length is a fact of the callee's perspective.
    750740In the caller's perspective, the type system is quite lax.
    751 Here, there is (some, but) little checking of what is being passed matches the parameter.
     741Here, there is (some, but) little checking that what is being passed, matches.
    752742% void f( float [][10] );
    753743% int n = 100;
    … …  
    784774void foo( float a[][10] ) { ... }                               $\C{// definition}$
    785775\end{cfa}
    786 Repeating it with the full context of a VLA is useful.
     776Repeating it with the full context of a VLA is useful:
    787777\begin{cfa}
    788778void foo( int, float [][@*@] );                                 $\C{// declaration}$
    … …  
    804794typedef long int jmp_buf[8];
    805795\end{cfa}
    806 An instance of this array can be declared as a structure field.
     796A instance of this array can be declared as a structure field.
    807797\begin{cfa}
    808798struct Jmp_Buf {
    … …  
    829819Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
    830820
    831 The links organize nodes into a particular kind of data structure, \eg queue, tree, hash table, \etc, with operations specific to that kind.
     821The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format.
    832822Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
    833823hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
    … …  
    838828
    839829This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
    840 Within this restricted space, all design-issue discussions assume the following invariants.
     830Within this restricted space, all design-issue discussions assume the following invariants;
     831alternatives to the assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
    841832\begin{itemize}
    842833        \item A doubly-linked list is being designed.
    … …  
    844835                Circular \vs ordered linking is discussed under List identity (\VRef{toc:lst:issue:ident}).
    845836        \item Link fields are system-managed.
     837                The user works with the system-provided API to query and modify list membership.
    846838                The system has freedom over how to represent these links.
    847                 The user works with the system-provided API to query and modify list membership.
    848839        \item The user data must provide storage for the list link-fields.
    849840                Hence, a list node is \emph{statically} defined as data and links \vs a node that is \emph{dynamically} constructed from data and links \see{\VRef{toc:lst:issue:attach}}.
    850841\end{itemize}
    851 Alternatives to these assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
    852842
    853843
    … …  
    855845\label{s:PreexistingLinked-ListLibraries}
    856846
    857 To show examples of the concepts being defined, two preexisting linked-list libraries are used throughout and further libraries are introduced as needed.
     847Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
     848and further libraries are introduced as needed.
    858849\begin{enumerate}
    859850        \item Linux Queue library~\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
    … …  
    861852\end{enumerate}
    862853%A general comparison of libraries' abilities is given under Related Work (\VRef{toc:lst:relwork}).
    863 For the discussion, assume the type @req@ (request) is the user's payload in examples.
    864 Then the job of a list library is to help a user manage (organize) requests, \eg a request can be a network arrival-event processed by a web browser or a thread blocked/scheduled by the runtime.
     854For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
     855As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival-event or scheduling a thread.
    865856
    866857
    … …  
    875866The wrapped style distinguishes between wrapping a reference and wrapping a value, \eg @list<req *>@ or @list<req>@.
    876867(For this discussion, @list<req &>@ is similar to @list<req *>@.)
    877 This difference is one of user style and performance (copying), not framework capability.
     868This difference is one of user style, not framework capability.
    878869Library LQ is intrusive; STL is wrapped with reference and value.
    879870
    … …  
    982973An example of an attribute on the link fields is cache alignment, possibly in conjunction with other @req@ fields, improving locality and/or avoiding false sharing.
    983974For example, if a list is frequently traversed in the forward direction, and infrequently gets elements removed at random positions, then an ideal layout for cache locality puts the forward links, together with frequently-used payload data on one cache line, leaving the reverse links on a colder cache line.
    984 In contrast, supplying link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes.
     975Supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes.
    985976Wrapped reference has no control over the link fields, but the separate data allows some control;
    986977wrapped value has no control over data or links.
    987978
    988979Another subtle advantage of intrusive arrangement is that a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
    989 In LQ, the intrusive @req@ pointer is the correct argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
     980In LQ, the intrusive @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
    990981there is no distinguishing a @req@ from a @req@ in a list.
    991982The same is not true of STL, wrapped reference or value.
    … …  
    998989Then, a novel use can put a @req@ in a list, without requiring any upstream change in the @req@ library.
    999990In intrusive, the ability to be listed must be planned during the definition of @req@.
    1000 Optimistically adding a couple links for future use is normally cheap because links are small and memory is big.
    1001991
    1002992\begin{figure}
    … …  
    10241014An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
    10251015A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
    1026 Like LQ, \CFA is capable of supporting a wrapped library, if need arose.
     1016\CFA is capable of supporting a wrapped library, if need arose.
    10271017
    10281018
    … …  
    11551145\subsection{User Integration: Preprocessed \vs Type-System Mediated}
    11561146
    1157 While the syntax for LQ is reasonably succinct, it comes at the cost of using C preprocessor macros for generics, which are not part of the language type-system, unlike \CC templates.
     1147While the syntax for LQ is reasonably succinct, it comes at the cost of using C preprocessor macros for generics, which are not part of the language type-system, like \CC templates.
    11581148Hence, small errors in macro arguments can lead to large substitution mistakes, as the arguments maybe textually written in many places and/or concatenated with other arguments/text to create new names and expressions.
    1159 Hence, textual expansion can lead to a cascade of error messages that are confusing and difficult to debug.
    1160 For example, argument errors like @a.b@{\Large\color{red},}@c@, comma instead of period, or @by@{\Large\color{red}-}@pri@, minus instead of underscore, can produce many error messages.
    1161 Note, similar problems exist for \CC templates.
    1162 
    1163 Instead, language function calls (even with inlining) handle argument mistakes locally at the call, giving very specific error message.
    1164 \CC @concepts@ were introduced in @templates@ to deal with this problem.
     1149This can lead to a cascade of error messages that are confusing and difficult to debug.
     1150For example, argument errors like @a.b,c@, comma instead of period, or @by-pri@, minus instead of underscore, can produce many error messages.
     1151
     1152Instead, language function calls (even with inlining) handled argument mistakes locally at the call, giving very specific error message.
     1153\CC @concepts@ were introduced in @templates@ to deal with just this problem.
    11651154
    11661155% example of poor error message due to LQ's preprocessed integration
    … …  
    11771166All examples so far use two distinct types for:
    11781167an item found in a list (type @req@ of variable @r1@, see \VRef[Figure]{fig:lst-issues-attach}), and the list (type @reql@ of variable @reqs_pri@, see \VRef[Figure]{fig:lst-issues-ident}).
    1179 This kind of list is \newterm{headed}, where the empty list is just a head.
    1180 An alternate ad-hoc approach omits the header, where the empty list is no nodes.
     1168This kind of list is ``headed'', where the empty list is just a head.
     1169An alternate ``ad-hoc'' approach omits the header, where the empty list is no nodes.
    11811170Here, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
    11821171Note, a headed list is superset of an ad-hoc list, and can normally perform all of the ad-hoc operations.
    … …  
    12131202Note, a list does not need to use links to denote its size;
    12141203it can use a node counter in the header, where $N$ node traversals indicates complete navigation of the list.
    1215 However, managing the number of nodes is an additional cost, whereas the links must always be managed.
     1204However, managing the number of nodes is an additional cost, as the links must always be managed.
    12161205
    12171206The following discussion refers to the LQ representations, detailed in \VRef[Figure]{fig:lst-issues-end}, using a null pointer to mark end points.
    … …  
    12621251
    12631252A C character constant is an ASCII/Latin-1 character enclosed in single-quotes, \eg @'x'@, @'@\textsterling@'@.
    1264 A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @'\u'@ identifies a universal character name.
    1265 A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@, form feed, a delimiter character @'\''@, embedded single quote, or a raw character @'\xa3'@, \textsterling.
     1253A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @\u@ identifies a universal character name.
     1254A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@ form feed, a delimiter character @'\''@ embedded single quote, or a raw character @'\xa3'@ \textsterling.
    12661255
    12671256A C character string is zero or more regular, wide, or escape characters enclosed in double-quotes @"xyz\n"@.
    1268 The kind of characters in the string is denoted by a prefix: wide characters are prefixed by @L@, @u@, or @U@; UTF-8 characters are prefixed by @u8@.
    1269 
     1257The kind of characters in the string is denoted by a prefix: UTF-8 characters are prefixed by @u8@, wide characters are prefixed by @L@, @u@, or @U@.
     1258
     1259For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabic Y-Cree OO).
    12701260For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multi-byte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wscanf@/@wprintf@.
    1271 The value of a wide-character is implementation defined, usually a UTF-16 character.
     1261The value of a wide-character is implementation-defined, usually a UTF-16 character.
    12721262For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with wide characters corresponding to the multi-byte character sequence, \eg @u"abc@$\mu$@"@, @U"abc@$\mu$@"@.
    12731263The value of a @"u"@ character is an UTF-16 character;
    12741264the value of a @"U"@ character is an UTF-32 character.
    1275 The value of a string literal containing a multi-byte character or escape sequence not represented in the execution character set is implementation defined.
    1276 For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabic Y-Cree OO).
     1265The value of a string literal containing a multi-byte character or escape sequence not represented in the execution character set is implementation-defined.
    12771266
    12781267C strings are null-terminated rather than maintaining a separate string length.
    … …  
    12841273This property is only preserved by the compiler with respect to character constants, \eg @"abc"@ is actually @"abc\0"@, \ie 4 characters rather than 3.
    12851274Otherwise, the compiler does not participate, making string operations both unsafe and inefficient.
    1286 For example, it is common in C to:
    1287 \begin{itemize}
    1288 \item
    1289 forget that a character constant is larger than it appears during manipulation,
    1290 \item
    1291 that extra storage is needed in a character array for the terminator,
    1292 \item
    1293 or that the terminator must be preserved during string operations, otherwise there are array overruns.
    1294 \end{itemize}
     1275For example, it is common in C to: forget that a character constant is larger than it appears during manipulation, that extra storage is needed in a character array for the terminator, or that the terminator must be preserved during string operations, otherwise there are array overruns.
    12951276Finally, the need to repeatedly scan an entire string to determine its length can result in significant cost, as it is impossible to cache the length in many cases, \eg when a string is passed into another function.
    12961277

  • doc/theses/mike_brooks_MMath/intro.tex

    r79ba50c r5e0b6657  
    11\chapter{Introduction}
    22
    3 All modern programming languages provide at least these three high-level containers (collections): array, linked-list, and string.
    4 Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
    5 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
     3All modern programming languages provide three high-level containers (collections): array, linked-list, and string.
     4Often array is part of the programming language, while linked-lists are built from (recursive) pointer types, and strings from a combination of array and linked-list.
     5For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
    66
    7 Unfortunately, memory misuse under C-idiomatic programming causes a significant number of errors~\cite{Oorschot23}.
     7Unfortunately, these three aspects of C cause a significant number of memory errors~\cite{Oorschot23}.
    88Estimates suggest 50\%~\cite{Mendio24} of total reported open-source vulnerabilities occurring in C result from errors using these facilities (memory errors).
    99For operating system and browser vendors, who heavily use systems languages, 60\%--70\% of reported software vulnerabilities involved memory errors~\cite{Kehrer23}.
    1010For Microsoft, 70\% of vulnerabilities addressed via security updates between 2006--2018 are memory safety issues~\cite[slide 10]{Miller19}.
    11 In a study of software exploits in the U.S. National Vulnerability Database over 2013--2017, the top reported vulnerability is buffer errors (in the sense of misused array bounds), among 19 vulnerability categories~\cite{Cifuentes19}.
     11In a study of software exploits in the U.S. National Vulnerability Database over 2013--2017, the top reported vulnerability is (memory) buffer errors, among 19 vulnerability categories~\cite{Cifuentes19}.
     12Therefore, hardening these three C types goes a long way to make the majority of C programs safer and eliminating major hacker attack-vectors.
    1213
    13 While these figures address memory errors, defined without limit to the three primary collections, these authors' explanations of memory errors, among other C analysis efforts, suggest improving on C's language/library options for working with these three collections would be widely beneficial.
    14 Every one of the safety-statistic sources above includes array bounds in its first characterization of unsafe programming-language features.
    15 Of the four studies that deal exclusively with memory safety (excluding~\cite{Cifuentes19}), all put @malloc@--@free@ upfront as well.
    16 The one that specifically surveys C features, \cite{Oorschot23}, also has similarly prominent blame on both of: the null-terminated text idiom, with its support/mandate in the C standard library; the unprotected nature of C pointers.
    17 An effort at translating C to safe Rust~\cite{Emre2022} has pointers as the stand-out difficult aspect to analyze.\footnote{
    18         \cite{Emre2022} demonstrates the difficulty of analyzing C pointers for safety (while tacking some of this difficult problem).
    19         It first puts a corpus of C programs through a naive Rust translation, which ``succeeds'' by leaving many uses of Rust's \lstinline{unsafe} marker.
    20         Then, it analyzes these uses and presents a technique for reducing those uses that hinge exclusively on referenced object lifetime.
    21         Pointer dereference accounts for 80\% of the cases that the naive translation did not make safe (Table 3.2, p33).
    22         Of these, 10\% are eligible for the work's own safety improvement technique, while this filtering leaves 75\% with no single cause of unsafety determined (Table 3.5, p39).
    23         The presented technique succeeds at making 75\% of the eligible initially unsafe dereferences safe, by inferring the necessary lifetime annotations (Table 4.2, p83).
    24         This result leaves, per 1000 LOC, 3.3 unremovable unsafe dereferences that are understood to evade lifetime analysis, among 220 gross unsafe dereferences (Tables 3.5, 4.2 and 3.1, p27).
    25         % 3.3 = 1398/413,428 * 1000
    26         % 220 ~= (99,101 [@tab3.5] - 9631 [@tab4.2] ) / 413,428 [@tab 3.1] * 1000
    27 }
    28 A tool for analyzing C code's use of linked data structures (including, \eg skip list and binary tree) found variations of the linked-list shape to be present in most of the programs in its corpus~\cite{White2016}.
    29 So, C's array unsafety is infamous, its string pattern necessitates explicit storage management (also infamous), and user-written linked lists are an attrictively recognizable player in the arena of (infamously) unsafe raw pointer uses.
    30 Therefore, hardening the three primary collections goes a long way to making the majority of C programs safer, and eliminating major hacker attack vectors.
    31 
    32 This work looks at extending these foundational container types in the programming language \CFA, which is a new dialect of the C programming language.
     14This work looks at extending these three foundational container types in the programming language \CFA, which is a new dialect of the C programming language.
    3315A primary goal of \CFA~\cite{Cforall} is 99\% backward compatibility with C, while maintaining a look and feel that matches with C programmer experience and intuition.
    3416This goal requires ``thinking inside the box'' to engineer new features that ``work and play'' with C and its massive legacy code-base.
    … …  
    4830
    4931C provides a simple array type as a language feature.
    50 However, it adopts the controversial position of treating pointer and array as twins, leading to multiple problems.
    51 The way that arrays are typicaly passed around a program removes the information necessary to do bound checks.
     32However, it adopts the controversial position of treating pointer and array as duals, leading to multiple problems.
    5233
    5334
    … …  
    6041otherwise, elements are heap allocated with internal or external link fields.
    6142
    62 C provides a few simple, library data-structures (@glibc@):
     43C provides a few simple, polymorphic, library data-structures (@glibc@):
    6344\begin{itemize}
    6445\item
    … …  
    6748hash search table consisting of a key (string) with associated data (@<search.h>@)
    6849\end{itemize}
    69 Because these container libraries can be restrictive or awkward to use, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
     50Because these container libraries can be restrictive, awkward to use, and unsafe, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
    7051
    7152

  • doc/theses/mike_brooks_MMath/programs/bkgd-c-tyerr.c

    r79ba50c r5e0b6657  
    1616
    1717        float pi = 3.14;
    18         void f( void (*g)(void) );
     18        void f( void (*g)(void) ) { g(); }
    1919        @f( &pi );@                     $\C{// wrong}$
    2020}

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c

    r79ba50c r5e0b6657  
    1010        assert( sizeof(pa0x) != sizeof(ar) );
    1111
    12         void f( @float x[10]@, @float * y@ ) {
     12        void f( float x[10], float * y ) {
    1313                static_assert( sizeof(x) == sizeof(void *) );
    1414                static_assert( sizeof(y) == sizeof(void *) );
    … …  
    1616        f( 0, 0 );
    1717
    18         // reusing local variable float ar[10]
     18        // reusing local var `float a[10];`}
    1919        float v;
    2020        f( ar, ar );                            $\C{// ok: two decays, one into an array spelling}$

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c

    r79ba50c r5e0b6657  
    3838//      float (*b[3])[10];
    3939        float * b[3];
    40         for ( int i = 0; i < 3; i ++ ) {
    41                 b[i] = malloc( sizeof( float[10] ) );
     40        for (int i = 0; i < 3; i ++) {
     41                b[i] = malloc(sizeof(float[10]));
    4242        }
    4343        mx[2][3];

  • doc/theses/mike_brooks_MMath/programs/lst-issues-multi-static.run.c

    r79ba50c r5e0b6657  
    2020struct req {
    2121        int pri, rqr;
    22         LIST_ENTRY( req ) by_pri;
    23         LIST_ENTRY( req ) by_rqr;
     22        LIST_ENTRY(req) by_pri;
     23        LIST_ENTRY(req) by_rqr;
    2424};
    2525
    26 LIST_HEAD( reql, req );
     26LIST_HEAD(reql, req);
    2727
    2828struct reql reqs_pri;
    … …  
    3131struct reql reqs_rqr_99;
    3232
    33 LIST_INIT( &reqs_pri );
    34 LIST_INIT( &reqs_rqr_42 );
    35 LIST_INIT( &reqs_rqr_17 );
    36 LIST_INIT( &reqs_rqr_99 );
     33LIST_INIT(&reqs_pri);
     34LIST_INIT(&reqs_rqr_42);
     35LIST_INIT(&reqs_rqr_17);
     36LIST_INIT(&reqs_rqr_99);
    3737
    3838struct req
    … …  
    4444        r99a = {3, 99};
    4545
    46 LIST_INSERT_HEAD( &reqs_pri, &r17c, by_pri );
    47 LIST_INSERT_HEAD( &reqs_pri, &r99a, by_pri );
    48 LIST_INSERT_HEAD( &reqs_pri, &r17b, by_pri );
    49 LIST_INSERT_HEAD( &reqs_pri, &r42b, by_pri );
    50 LIST_INSERT_HEAD( &reqs_pri, &r17a, by_pri );
    51 LIST_INSERT_HEAD( &reqs_pri, &r42a, by_pri );
     46LIST_INSERT_HEAD(&reqs_pri, &r17c, by_pri);
     47LIST_INSERT_HEAD(&reqs_pri, &r99a, by_pri);
     48LIST_INSERT_HEAD(&reqs_pri, &r17b, by_pri);
     49LIST_INSERT_HEAD(&reqs_pri, &r42b, by_pri);
     50LIST_INSERT_HEAD(&reqs_pri, &r17a, by_pri);
     51LIST_INSERT_HEAD(&reqs_pri, &r42a, by_pri);
    5252
    53 LIST_INSERT_HEAD( &reqs_rqr_42, &r42b, by_rqr );
    54 LIST_INSERT_HEAD( &reqs_rqr_42, &r42a, by_rqr );
     53LIST_INSERT_HEAD(&reqs_rqr_42, &r42b, by_rqr);
     54LIST_INSERT_HEAD(&reqs_rqr_42, &r42a, by_rqr);
    5555
    56 LIST_INSERT_HEAD( &reqs_rqr_17, &r17c, by_rqr );
    57 LIST_INSERT_HEAD( &reqs_rqr_17, &r17b, by_rqr );
    58 LIST_INSERT_HEAD( &reqs_rqr_17, &r17a, by_rqr );
     56LIST_INSERT_HEAD(&reqs_rqr_17, &r17c, by_rqr);
     57LIST_INSERT_HEAD(&reqs_rqr_17, &r17b, by_rqr);
     58LIST_INSERT_HEAD(&reqs_rqr_17, &r17a, by_rqr);
    5959
    60 LIST_INSERT_HEAD( &reqs_rqr_99, &r99a, by_rqr );
     60LIST_INSERT_HEAD(&reqs_rqr_99, &r99a, by_rqr);
    6161
    6262
    … …  
    6767
    6868struct req *cur;
    69 LIST_FOREACH( cur, &reqs_pri, by_pri )
    70         printf( "{%d %d} ", cur->pri, cur->rqr );
    71 printf( "| " );
    72 LIST_FOREACH( cur, &reqs_rqr_42, by_rqr )
    73         printf( "{%d %d} ", cur->pri, cur->rqr );
    74 printf( "| " );
    75 LIST_FOREACH( cur, &reqs_rqr_17, by_rqr )
    76         printf( "{%d %d} ", cur->pri, cur->rqr );
    77 printf( "| " );
    78 LIST_FOREACH( cur, &reqs_rqr_99, by_rqr )
    79         printf( "{%d %d} ", cur->pri, cur->rqr );
    80 printf( "\n" );
     69LIST_FOREACH(cur, &reqs_pri, by_pri)
     70        printf("{%d %d} ", cur->pri, cur->rqr);
     71printf("| ");
     72LIST_FOREACH(cur, &reqs_rqr_42, by_rqr)
     73        printf("{%d %d} ", cur->pri, cur->rqr);
     74printf("| ");
     75LIST_FOREACH(cur, &reqs_rqr_17, by_rqr)
     76        printf("{%d %d} ", cur->pri, cur->rqr);
     77printf("| ");
     78LIST_FOREACH(cur, &reqs_rqr_99, by_rqr)
     79        printf("{%d %d} ", cur->pri, cur->rqr);
     80printf("\n");
    8181
    8282}

  • doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

    r79ba50c r5e0b6657  
    131131\CFA strives to fix mistakes in C, chief among them, safety.
    132132This thesis presents a significant step forward in \CFA's goal to remove unsafe pointer operations.
    133 It describes improvements to the \CFA language design to support advanced container features.
    134 These features are implemented across the \CFA compiler and runtime libraries.
    135 The results maintain another \CFA goal of offering strong backwards compatibility with C.
    136 This work leverages preexisting \CFA contributiongs of prior students working on the \CFA project, particularly through novel applications of the compiler's type system.
    137 
    138 All modern programming languages provide at least these three high-level containers (collections): array, linked-list, and string.
    139 Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
    140 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
    141 Unfortunately, typical solutions for the the key types in C cause 60\%--70\% of the reported software vulnerabilities involving memory errors; 70\%--80\% of hacker attack vectors target these types.
     133The thesis presents improvements to the \CFA language design, both syntax and semantics, to support advanced container features.
     134These features are implemented across the \CFA compiler, libraries, and runtime system.
     135The results maintain another \CFA goal of remaining 99\% backwards compatible with C.
     136This thesis leverages preexisting work within the compiler's type and runtime systems generated by prior students working on the \CFA project.
     137
     138All modern programming languages provide three high-level containers (collections): array, linked-list, and string.
     139Often array is part of the programming language, while linked-lists are built from (recursive) pointer types, and strings from a combination of array and linked-list.
     140For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
     141Unfortunately, these three aspects of C cause 60\%--70\% of the reported software vulnerabilities involving memory errors, and 70\%--80\% of hacker attack-vectors target these types.
    142142Therefore, hardening these three C types goes a long way to make the majority of C programs safer.
    143143
    144144Specifically, an array utility is provided that tracks length internally, relieving the user of managing explicit length parameters and stopping buffer-overrun errors.
    145145This feature requires augmenting the \CFA type system, making array length available at compile and runtime.
    146 A linked-list utility is provided, which obviates many user-managed recursive pointers by catering directly to system-programming uses (intrusive linking, ad-hoc listing) for which a library solution is often dismissed.
     146A linked-list utility is provided, which obviates many explicit recursive pointers by catering directly to system-programming uses (intrusive lists) for which a library solution is often dismissed.
    147147Finally, a string utility is provided with implicit memory management of text in a specialized heap, relieving error-prone buffer management, including overrun, and providing a copy-on-write speed boost.
    148148For all three utilities, performance is argued to be on-par with, and occasionally surpassing relevant comparators.

  • doc/theses/mike_brooks_MMath/uw-ethesis.bib

    r79ba50c r5e0b6657  
    9494}
    9595
    96 % -------------------------------------------------
    97 % Safety
    98 
    9996@article{Blache19,
    10097    author      = {Gunter Blache},
    … …  
    125122}
    126123
    127 @phdthesis{Emre2022,
    128     author  = "Mehmet Emre",
    129     title   = "Translating C to Safe Rust: Reasoning about Pointer Types and Lifetimes",
    130     school  = "UC Santa Barbara",
    131     year    = "2022"
    132 }
    133 
    134 @inproceedings{White2016,
    135     author = {White, David H. and Rupprecht, Thomas and L\"{u}ttgen, Gerald},
    136     title = {DSI: an evidence-based approach to identify dynamic data structures in C programs},
    137     year = {2016},
    138     isbn = {9781450343909},
    139     publisher = {Association for Computing Machinery},
    140     address = {New York, NY, USA},
    141     url = {https://doi.org/10.1145/2931037.2931071},
    142     doi = {10.1145/2931037.2931071},
    143     booktitle = {Proceedings of the 25th International Symposium on Software Testing and Analysis},
    144     pages = {259–269},
    145     numpages = {11},
    146     keywords = {Data structure identification, dynamic data structures, pointer programs, program comprehension},
    147     location = {Saarbr\"{u}cken, Germany},
    148     series = {ISSTA 2016}
    149 }
    150 
    151 % -----------------------------------------------
    152 % Misc
    153 
    154124@misc{RVO20,
    155125    contributer = {pabuhr@plg},
    … …  
    179149    howpublished= {\url{https://c-faq.com/decl/spiral.anderson.html}},
    180150}
    181 
Note: See TracChangeset for help on using the changeset viewer.