1 //: Addresses help us spend less time copying data around.
  2 
  3 //: So far we've been operating on primitives like numbers and characters, and
  4 //: we've started combining these primitives together into larger logical
  5 //: units (containers or arrays) that may contain many different primitives at
  6 //: once. Containers and arrays can grow quite large in complex programs, and
  7 //: we'd like some way to efficiently share them between recipes without
  8 //: constantly having to make copies. Right now 'next-ingredient' and 'return'
  9 //: copy data across recipe boundaries. To avoid copying large quantities of
 10 //: data around, we'll use *addresses*. An address is a bookmark to some
 11 //: arbitrary quantity of data (the *payload*). It's a primitive, so it's as
 12 //: efficient to copy as a number. To read or modify the payload 'pointed to'
 13 //: by an address, we'll perform a *lookup*.
 14 //:
 15 //: The notion of 'lookup' isn't an instruction like 'add' or 'subtract'.
 16 //: Instead it's an operation that can be performed when reading any of the
 17 //: ingredients of an instruction, and when writing to any of the products. To
 18 //: write to the payload of an ingredient rather than its value, simply add
 19 //: the /lookup property to it. Modern computers provide efficient support for
 20 //: addresses and lookups, making this a realistic feature.
 21 //:
 22 //: To recap: an address is a bookmark to some potentially large payload, and
 23 //: you can replace any ingredient or product with a lookup to an address of
 24 //: the appropriate type. But how do we get addresses to begin with? That
 25 //: requires a little more explanation. Once we introduce the notion of
 26 //: bookmarks to data, we have to think about the life cycle of a piece of
 27 //: data and its bookmarks (because remember, bookmarks can be copied around
 28 //: just like anything else). Otherwise several bad outcomes can result (and
 29 //: indeed *have* resulted in past languages like C):
 30 //:
 31 //:   a) You can run out of memory if you don't have a way to reclaim
 32 //:   data.
 33 //:   b) If you allow data to be reclaimed, you have to be careful not to
 34 //:   leave any stale addresses pointing at it. Otherwise your program might
 35 //:   try to lookup such an address and find something unexpected. Such
 36 //:   problems can be very hard to track down, and they can also be exploited
 37 //:   to break into your computer over the network, etc.
 38 //:
 39 //: To avoid these problems, we introduce the notion of a *reference count* or
 40 //: refcount. The life cycle of a bit of data accessed through addresses looks
 41 //: like this.
 42 //:
 43 //:    We create space in computer memory for it using the 'new' instruction.
 44 //:    The 'new' instruction takes a type as an ingredient, allocates
 45 //:    sufficient space to hold that type, and returns an address (bookmark)
 46 //:    to the allocated space.
 47 //:
 48 //:      x:address:num <- new number:type
 49 //:
 50 //:                     +------------+
 51 //:          x -------> |  number    |
 52 //:                     +------------+
 53 //:
 54 //:    That isn't entirely accurate. Under the hood, 'new' allocates an extra
 55 //:    number -- the refcount:
 56 //:
 57 //:                     +------------+------------+
 58 //:          x -------> | refcount   |  number    |
 59 //:                     +------------+------------+
 60 //:
 61 //:    This probably seems like a waste of space. In practice it isn't worth
 62 //:    allocating individual numbers and our payload will tend to be larger,
 63 //:    so the picture would look more like this (zooming out a bit):
 64 //:
 65 //:                         +-------------------------+
 66 //:                     +---+                         |
 67 //:          x -------> | r |                         |
 68 //:                     +---+        DATA             |
 69 //:                         |                         |
 70 //:                         |                         |
 71 //:                         +-------------------------+
 72 pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module ranger.shared.settings</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head><body bgcolor="#f0f0f8">

<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial">&nbsp;<br><big><big><strong><a href="ranger.html"><font color="#ffffff">ranger</font></a>.<a href="ranger.shared.html"><font color="#ffffff">shared</font></a>.settings</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/hut/work/ranger/ranger/shared/settings.py">/home/hut/work/ranger/ranger/shared/settings.py</a></font></td></tr></table>
    <p><tt>#&nbsp;Copyright&nbsp;(c)&nbsp;2009,&nbsp;2010&nbsp;hut&nbsp;&lt;hut@lavabit.com&gt;<br>
#<br>
#&nbsp;Permission&nbsp;to&nbsp;use,&nbsp;copy,&nbsp;modify,&nbsp;and/or&nbsp;distribute&nbsp;this&nbsp;software&nbsp;for&nbsp;any<br>
#&nbsp;purpose&nbsp;with&nbsp;or&nbsp;without&nbsp;fee&nbsp;is&nbsp;hereby&nbsp;granted,&nbsp;provided&nbsp;that&nbsp;the&nbsp;above<br>
#&nbsp;copyright&nbsp;notice&nbsp;and&nbsp;this&nbsp;permission&nbsp;notice&nbsp;appear&nbsp;in&nbsp;all&nbsp;copies.<br>
#<br>
#&nbsp;THE&nbsp;SOFTWARE&nbsp;IS&nbsp;PROVIDED&nbsp;"AS&nbsp;IS"&nbsp;AND&nbsp;THE&nbsp;AUTHOR&nbsp;DISCLAIMS&nbsp;ALL&nbsp;WARRANTIES<br>
#&nbsp;WITH&nbsp;REGARD&nbsp;TO&nbsp;THIS&nbsp;SOFTWARE&nbsp;INCLUDING&nbsp;ALL&nbsp;IMPLIED&nbsp;WARRANTIES&nbsp;OF<br>
#&nbsp;MERCHANTABILITY&nbsp;AND&nbsp;FITNESS.&nbsp;IN&nbsp;NO&nbsp;EVENT&nbsp;SHALL&nbsp;THE&nbsp;AUTHOR&nbsp;BE&nbsp;LIABLE&nbsp;FOR<br>
#&nbsp;ANY&nbsp;SPECIAL,&nbsp;DIRECT,&nbsp;INDIRECT,&nbsp;OR&nbsp;CONSEQUENTIAL&nbsp;DAMAGES&nbsp;OR&nbsp;ANY&nbsp;DAMAGES<br>
#&nbsp;WHATSOEVER&nbsp;RESULTING&nbsp;FROM&nbsp;LOSS&nbsp;OF&nbsp;USE,&nbsp;DATA&nbsp;OR&nbsp;PROFITS,&nbsp;WHETHER&nbsp;IN&nbsp;AN<br>
#&nbsp;ACTION&nbsp;OF&nbsp;CONTRACT,&nbsp;NEGLIGENCE&nbsp;OR&nbsp;OTHER&nbsp;TORTIOUS&nbsp;ACTION,&nbsp;ARISING&nbsp;OUT&nbsp;OF<br>
#&nbsp;OR&nbsp;IN&nbsp;CONNECTION&nbsp;WITH&nbsp;THE&nbsp;USE&nbsp;OR&nbsp;PERFORMANCE&nbsp;OF&nbsp;THIS&nbsp;SOFTWARE.</tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
    
<tr><td bgcolor="#ee77aa"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="builtins.html#object">builtins.object</a>
</font></dt><dd>
<dl>
<dt><font face="helvetica, arial"><a href="ranger.shared.settings.html#SettingsAware">SettingsAware</a>
</font></dt></dl>
</dd>
</dl>
 <p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#000000" face="helvetica, arial"><a name="SettingsAware">class <strong>SettingsAware</strong></a>(<a href="builtins.html#object">builtins.object</a>)</font></td></tr>
    
<tr><td bgcolor="#ffc8d8"><tt>&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%">Data descriptors defined here:<br>
<dl><dt><strong>__dict__</strong></dt>
<dd><tt>dictionary&nbsp;for&nbsp;instance&nbsp;variables&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<dl><dt><strong>__weakref__</strong></dt>
<dd><tt>list&nbsp;of&nbsp;weak&nbsp;references&nbsp;to&nbsp;the&nbsp;object&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<hr>
Data and other attributes defined here:<br>
<dl><dt><strong>settings</strong> = &lt;ranger.ext.openstruct.OpenStruct object at 0x7f6a9067fbd0&gt;</dl>

</td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#55aa55">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Data</strong></big></font></td></tr>
    
<tr><td bgcolor="#55aa55"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><strong>ALLOWED_SETTINGS</strong> = ['show_hidden', 'scroll_offset', 'directories_first', 'sort', 'reverse', 'preview_files', 'max_history_size', 'colorscheme', 'collapse_preview', 'max_dirsize_for_autopreview', 'autosave_bookmarks', 'apps', 'keys']</td></tr></table>
</body></html>
limiter">, r).name << end(); 276 for (int i = 0; i < SIZE(get(Recipe, r).steps); ++i) { 277 instruction& inst = get(Recipe, r).steps.at(i); 278 // Convert 'new' To 'allocate' 279 if (inst.name == "new") { 280 inst.operation = ALLOCATE; 281 type_tree* type = new_type_tree(inst.ingredients.at(0).name); 282 inst.ingredients.at(0).set_value(size_of(type)); 283 trace(9992, "new") << "size of '" << inst.ingredients.at(0).name << "' is " << inst.ingredients.at(0).value << end(); 284 delete type; 285 } 286 } 287 } 288 289 //: implement 'allocate' based on size 290 291 :(before "End Globals") 292 extern const int Reserved_for_tests = 1000; 293 int Memory_allocated_until = Reserved_for_tests; 294 int Initial_memory_per_routine = 100000; 295 :(before "End Setup") 296 Memory_allocated_until = Reserved_for_tests; 297 Initial_memory_per_routine = 100000; 298 :(before "End routine Fields") 299 int alloc, alloc_max; 300 :(before "End routine Constructor") 301 alloc = Memory_allocated_until; 302 Memory_allocated_until += Initial_memory_per_routine; 303 alloc_max = Memory_allocated_until; 304 trace(9999, "new") << "routine allocated memory from " << alloc << " to " << alloc_max << end(); 305 306 :(before "End Primitive Recipe Declarations") 307 ALLOCATE, 308 :(before "End Primitive Recipe Numbers") 309 put(Recipe_ordinal, "allocate", ALLOCATE); 310 :(before "End Primitive Recipe Implementations") 311 case ALLOCATE: { 312 // compute the space we need 313 int size = ingredients.at(0).at(0); 314 if (SIZE(ingredients) > 1) { 315 // array allocation 316 trace(9999, "mem") << "array length is " << ingredients.at(1).at(0) << end(); 317 size = /*space for length*/1 + size*ingredients.at(1).at(0); 318 } 319 int result = allocate(size); 320 if (SIZE(current_instruction().ingredients) > 1) { 321 // initialize array length 322 trace(9999, "mem") << "storing " << ingredients.at(1).at(0) << " in location " << result+/*skip refcount*/1 << end(); 323 put(Memory, result+/*skip refcount*/1, ingredients.at(1).at(0)); 324 } 325 products.resize(1); 326 products.at(0).push_back(result); 327 break; 328 } 329 :(code) 330 int allocate(int size) { 331 // include space for refcount 332 ++size; 333 trace(9999, "mem") << "allocating size " << size << end(); 334 //? Total_alloc += size; 335 //? ++Num_alloc; 336 // Allocate Special-cases 337 // compute the region of memory to return 338 // really crappy at the moment 339 ensure_space(size); 340 const int result = Current_routine->alloc; 341 trace(9999, "mem") << "new alloc: " << result << end(); 342 // initialize allocated space 343 for (int address = result; address < result+size; ++address) { 344 trace(9999, "mem") << "storing 0 in location " << address << end(); 345 put(Memory, address, 0); 346 } 347 Current_routine->alloc += size; 348 // no support yet for reclaiming memory between routines 349 assert(Current_routine->alloc <= Current_routine->alloc_max); 350 return result; 351 } 352 353 //: statistics for debugging 354 //? :(before "End Globals") 355 //? int Total_alloc = 0; 356 //? int Num_alloc = 0; 357 //? int Total_free = 0; 358 //? int Num_free = 0; 359 //? :(before "End Setup") 360 //? Total_alloc = Num_alloc = Total_free = Num_free = 0; 361 //? :(before "End Teardown") 362 //? cerr << Total_alloc << "/" << Num_alloc 363 //? << " vs " << Total_free << "/" << Num_free << '\n'; 364 //? cerr << SIZE(Memory) << '\n'; 365 366 :(code) 367 void ensure_space(int size) { 368 if (size > Initial_memory_per_routine) { 369 tb_shutdown(); 370 cerr << "can't allocate " << size << " locations, that's too much compared to " << Initial_memory_per_routine << ".\n"; 371 exit(0); 372 } 373 if (Current_routine->alloc + size > Current_routine->alloc_max) { 374 // waste the remaining space and create a new chunk 375 Current_routine->alloc = Memory_allocated_until; 376 Memory_allocated_until += Initial_memory_per_routine; 377 Current_routine->alloc_max = Memory_allocated_until; 378 trace(9999, "new") << "routine allocated memory from " << Current_routine->alloc << " to " << Current_routine->alloc_max << end(); 379 } 380 } 381 382 :(scenario new_initializes) 383 % Memory_allocated_until = 10; 384 % put(Memory, Memory_allocated_until, 1); 385 def main [ 386 1:address:num <- new number:type 387 ] 388 +mem: storing 0 in location 10 389 390 :(scenario new_size) 391 def main [ 392 11:address:num/raw <- new number:type 393 12:address:num/raw <- new number:type 394 13:num/raw <- subtract 12:address:num/raw, 11:address:num/raw 395 ] 396 # size of number + refcount 397 +mem: storing 2 in location 13 398 399 :(scenario new_array_size) 400 def main [ 401 1:address:array:num/raw <- new number:type, 5 402 2:address:num/raw <- new number:type 403 3:num/raw <- subtract 2:address:num/raw, 1:address:array:num/raw 404 ] 405 # 5 locations for array contents + array length + refcount 406 +mem: storing 7 in location 3 407 408 :(scenario new_empty_array) 409 def main [ 410 1:address:array:num/raw <- new number:type, 0 411 2:address:num/raw <- new number:type 412 3:num/raw <- subtract 2:address:num/raw, 1:address:array:num/raw 413 ] 414 +run: {1: ("address" "array" "number"), "raw": ()} <- new {number: "type"}, {0: "literal"} 415 +mem: array length is 0 416 # one location for array length, and one for the refcount 417 +mem: storing 2 in location 3 418 419 //: If a routine runs out of its initial allocation, it should allocate more. 420 :(scenario new_overflow) 421 % Initial_memory_per_routine = 3; // barely enough room for point allocation below 422 def main [ 423 1:address:num/raw <- new number:type 424 2:address:point/raw <- new point:type # not enough room in initial page 425 ] 426 +new: routine allocated memory from 1000 to 1003 427 +new: routine allocated memory from 1003 to 1006