the first automation was written language

2020.7.28..31: adds/cs/the first automation was written language:
here is what humans have over other animals:
. our language uses symbols that can entirely describe
our understanding of the world;
and our understanding of the world is so vast
that we can survive without adapting our genome
by engineering environmental adaptations.
. also,
language in its written form is
more important than speech (the verbal form);
because it represents a form of automation of our memory;
giving us not only communication
but a virtually infinite memory size.
. the first reliable computations involved
writing the steps of an algorithm
so that we could automate the part of our mind
that remembered each step and their ordering.

target-owning vs aliasing pointers

12.7: summary:
. this explores types of pointers
needed for adda's space-efficient style of oop,
and support of safe pointers .

mem'mgt for a top-down stack layout

9.4: adda/mem'mgt/top-down stack layout:
[11.23: intro:
. the adda`oop system (unlike other oop impl's)
seeks to avoid generating garbage,
and that requires that when a function returns an object,
the return-obj's needed memory was allocated by the caller,
and then the function was given a pointer to that memory .
. that means assignments and function calls
are fused into one operation;
y`= f(x) is implicitly:
y`= f(x, ptr to y),
and this is true even when y is a parameter:
g( f(x) ) is implicitly:
stack g(y); stack f(x, ptr to y); call f; call g .

stackless mem'mgt

9.3: adda/mem'mgt/stackless:
[11.20: what stackless python does:
. a tasklet is like a separate program:
it has its own stack,
but for multi-threading it also
shares some state with some other program  .
. pickling is the saving of a running program
into a file until needed,
when the file is unpickled to become
the same running program it was before .
pickling stackless python's tasklets:
This allows you to take a tasklet mid-execution,
serialise it to a chunk of data
and then unserialise that data at a later point,
creating a new tasklet from it
that resumes where the last left off.]

. stackless python allows simulation of the stack,
so it can freeze your program's long operation,
and restart it when you have the computer back .
. even though we cannot freeze the C`stack,
we can impl' our own stack .
. see also notes on a system for ensuring
user interaction was not interrupted by
a long operation from an uncooperative subprogram
(in our system for ensuring this,
the compiler is rewriting each subprogram
by sprinkling it with calls to the gui;
so that no subprogram causes the gui to be
starved for cpu time).

semi-type-specific subheaps

14: adda/oop/type-specific heaps:
[29: intro:
. in a type-specific heap,
each object reference has 2 parts:
# an ID of the type it belongs to,
# a serial number unique to that type . 31:
. this promotes encapsulation,
because the reference isn't a pointer,
the only one who knows the object's address
is the type mgt that owns the object .
]
. given the idea of type-specific heaps,
how does that mix with adda's oop?
--that's the efficient form of oop;
the inefficient way of doing oop
uses garbage collection
and that is a choice independent of
which heap an object is owned by,
whether local or global .
. using pointers is not what causes
pointer semantics and garbage:
that's caused when assignments are overwriting
the pointer instead of the pointer's target:
to avoid garbage collection,
assignments need to overwrite the objects themselves
not the pointers to the objects .
. instead of a global type-specific heap
local vars would be placed into
the subprogram's local heap
that can have within it type-specific subheaps .

combined hardware-virtual isolation

addm/security/combined hardware-virtual isolation:
2.9: 3.31: intro:

. certain attributes of data are essential to security;
eg, by retagging arbitrary data so that it is
usable as a pointer to code,
we can treat malware data as instructions to follow .
. generally all data can be tagged
just as it is done by xml .

. there are 2 possible ways to enforce
process isolation and ROM attributes:
# HW (hardware) mem'mgt,
# VM (virtual machine) mem'mgt .
. hardware mem'mgt can enforce VM mem'mgt:
the VM's run-time exec never needs to change;
so, HW mem'mgt can see that code as const;
also, any file that the VM is trying to interpret
can be treated by the HW mem'mgt as
something that only the VM process can modify .
. finally, the VM has its own process space
and this should keep other processes
from corrupting its work space .

parasail is big win for reliable concurrency

12.7.2: news.adda/co/ParaSail
(Parallel Spec and Impl Lang) is by Ada's Tucker Taft:

first siting of parasail:
11/09/11 Language Lessons: Where New
Parallel Developments Fit Into Your Toolkit

By John Moore for Intelligence In Software
The rise of multicore processors and programmable GPUs
has sparked a wave of developments in
parallel programming languages.
Developers seeking to exploit multicore and manycore systems
-- potentially thousands of processors --
now have more options at their disposal.
Parallel languages making moves of late
include the SEJITS of University of California, Berkeley;
The Khronos Group’s OpenCL;
the recently open-sourced Cilk Plus;
and the newly created ParaSail language.
Developers may encounter these languages directly,
though the wider community will most likely find them
embedded within higher-level languages.

. ParaSail incorporates formal methods such as
preconditions and post-conditions,
which are enforced by the compiler.
In another nod to secure, safety-critical systems,

explorations of virtual memory

7.1: adda/vmem'mgt/intro:

. in our virtual memory stack system
we are replacing each of the stack's
subprogram activation records (act'rec's)
with a pointer to a resizable object
(ie, it points to an expandable array in the heap );
thus, the stack [8.29:
-- if we didn't have a stackless architecture -- ]
becomes an array of pairs:
( return address
, pointer to act'rec
) . if our allotted ram is getting full,
we can file the obj's attached to earlier parts of the stack
or even file earlier segments of a very long stack .

enforce mem limits or support vmem

5.15: adda/mem'mgt/enforce limits or support vmem:
. how to handle the situation where
a process may use too much memory ?
how do we set limits ?
. if a subprogram has a large job,
it might get a warning exception
and its exception handler for that
wants to offer to OS some reassurance:
just like it should be telling user how far along the job is,
each subprogram needs to declare a
max memory usage intention,
or know of the default max,
or handle the max'd-mem.exception
with a percentage of work done .

. another strategy for avoiding memory limits
is to implement our own virtual memory,
so that unused local heaps can be stored ....
. the c heap provides only a finite virtual memory:
each process may have a 4gb vmem limit .
. so, we need to get around this limit
by using files to store our memory;
then we only need to keep an eye on harddisk limits .

large trees composed of byte-ptr trees

1.8: adda/mem'mgt/
large trees composed of byte-ptr trees:
. part of a space-saving obssession has been
finding how to make large trees be composed of
small trees that can use byte-sized pointers .
. the large tree is just like the local heap space:
a function activation record is given one segment
in which to store local data and param's;
after that fills up, it's turned into rib of a backbone segment:
(an array of c pointers to other segs).
. the way this is arranged should be such that
we can refer to the rib segs as indexes of the base seg,
. if all those fill up, then the last seg is the next size up:
. say the backbone hold 10ribs of size 10,
then the last rib is 10x10 size.
...
. isn't this supposed to be building the same way numbers do?
after the backbone fills up, it needs to be extended from above;
ie, replace the seg tree with a new backbone seg,
and then make the full backbone seg
a child of the new backbone seg:
====
|
====
| | | | | .

1.23: adda/type"tree/packing smaller trees:
. you can build a tree in large array
and if detecting under 255,
do a straight copy to small: for 1..256: copy word to byte
because the same links apply using the same structure
only smaller pointers .

alloc'order and size

6.2: adda/mem'mgt/alloc'order and size:
. when using the c lang's dynamic mem'allocator (malloc)
the c`runtime assumes you will be
returning mem in mostly the same order as
when you obtained them .
. if this is not the case,
then there could be heap fragmentation problems .
[6.3:
. use of malloc order may be less complicated
because in modern systems there is v.mem,
so the parts of heap that are
in the way of compacting it
can simply be paged out .]

. the less mem you use at any one time,
the better chance buggy programs around you
don't blow up from exceeding mem limits .

. if needing to alloc mem in a way that could
cause heap fragmentation,
consider how much mem your program is using at once,
and whether you can break it into pieces
that do inout on temp files .

6.17: other strategies:
# at the app level:
. it's easier to find mem even in a fragmented heap
if you're decomposing your mem needs into smaller parts;
eg, instead of alloc'ing 100 contiguous words
for a 10x10 matrix,
you could do 10 alloc's of 10 words each
arranged as an array of pointer to arrays .
# at the os level:
. just as logical files are strings of
many non-contiguous physical mem blocks;
malloc could be impl'ing large mem requests
as strings of smaller mem blocks .

byte-sized pointers

1.18: adda/dstr/byte-sized pointers:
. keep pointers small by seeing large lists
as subtrees;
one of the node types of a tree is
"(this subtree root declares a new subheap:
it includes access to a 256-size array of tree node).
. how does that scale? it does because
root of huge subtree had its own subheap
where all terminal nodes were tagged as
(this is a sys'ptr [32bit c pointer]
-- not a pair of byte-sized tree ptrs [byte'ptr])
[1.31:
. as the tree progresses downward with fanout,
it eventually consumes 256 nodes;
any tree-building further down
must be done from a new-subheap node`type
(ie, a node whose purpose is to declare that
the following subtree is based in a new subheap).
. lets say that a tree uses
2 subheaps worth of nodes;
then if the tree is balanced,
it can be built with only 2 new-subheap nodes
by putting the left and right subtrees
each in their own subheap;
if the tree is not balanced,
then space efficiency requires that subheaps be shareable,
so that many smaller subtrees can be
impl'd on the same subheap .
. to make best use of space,
the use of new-subheap node`types
must be minimized because they are overhead .]

. when having a ptr to subtree,
it needs a record:
sys`ptr to the subheap,
byte'ptr to where in the subheap subtree is rooted .

. when building trees from text, [1.31:
or when trees can be modified? ..]
then we need speed more than mem'
whereas figuring out how to pack for byte-ptr's
would be very time-consuming;
so, then these sort of trees should be word-sized .
. both sizes are distinguished from sys'pointers
with the term "(local ptr):
whereas a system pointer is logically a machine address
(practically an index into a process module),
a local ptr is always an index into the current subheap .
1.31:
. our tree node has less than 16 variants,
so the tag can fit in 4bits (a half-byte, nibble,
-- addressing a byte to extract the {hi,lo} 4bits );
the node's data will be sizes larger than a nibble,
and the tag should be at the beginning
to tell us what the rest of the node looks like;
so, in order to accommodate mem'allignment requirements,
without wasteful padding after the tag,
the subheap will have 2 forks
so that tags and data can each be
in their own arrays .

. a subheap supporting byte-ptr's
can hold only 256 nodes,
in turn needing a 128-byte chunk for the 256 * 4bit tags .
. these nodes are word sized:
#branch: (tag, left.byte-ptr, right.byte-ptr);
#leaf: (tag, symbol.word-ptr).

. subheaps are composed of chunks;
so, if a subheap is not enirely used,
it's not entirely alloc'd either .
. both byte-ptr and word-ptr subheaps
can use the same size chunks, 128 bytes,
to match the minimum chunk needed for tags .
. therefore 256*2byte data nodes = 128*2*2 = 4 chunks .
. if less than half of nodes are used,
then it can save on 2 chunks of 128 bytes .

. finally, a byte-ptr subheap needs to be
an array of 5 sys'pointers for access to the
1 tag chunk + 4 data chunks,
plus
whatever else is needed for variant tagging,
or part of an efficiency hack .

. if a large structure has a known minimum at init' time,
then it can be given a superchunk,
which is some arbitrary multiple of contiguous chunks .

roll-your-own heap systems

10.5: news.adda/app'based heaps more vulnerable:

Adobe Reader's Custom Memory Management: a Heap of Trouble
Research and Analysis: Haifei Li
Contributor and Editor: Guillaume Lovet
 a PDF-specific exploitation research
 focusing on the custom heap management on Adobe Reader.
summary:

. I filed this note under adda
because that is my C code generator,
the basis of addx,
whose design includes rolling its own
heap mgt system .
. this paper was pointing out that
the modern OS has a secure heap due to
randomization -- a feature I hadn't planned
to incorporate into the addx mem system .

"(performance sometimes
being the enemy of security,
this custom heap management system
makes it significantly easier
to exploit heap corruption flaws
in a solid and reliable way.
Coupled with the recent developments in
DEP(data execution prevention) protection bypass,
this makes heap corruption exploitation
possible across very many setups )

. if malware can overwrite your heap,
then it helps to have a hardened heap
(like what would typically be provided
by your platform's os).
. questions I had were
how are these happening ?
here's their skeletal answer:

"( Heap corruption flaws are initiated by
(Heap overflow, use after free,
integer overflow, etc...);
the two main ways to exploit these flaws:
# overwrite some app-provided data in the heap;
# corrupting Heap mgt system's internals
(eg: block headers, etc...)
so as to make the system itself
overwrite "interesting" data;
for instance, during blocks unlinking operations,
where several pointers are updated.)

. how is malware there in the first place
waiting for a priv'escalation?
. if you prevented all these:
(Heap overflow, use after free,
integer overflow);
what else is there?
is it that functions don't check inputs?
"(many PDF vulnerabilities out there
are structure-based ones, (i.e. file format))or can malware jump in the middle of your code?
aren't you cooked already?
[11.14:
. their crashing data becomes code
because it's overwriting your code:
the heap pointers you use
for going to your own code .]