doc/protocols/2009-02-11-s2s-memory.txt

   1 S2S Parser                                    OpenStranded Development Protocol
   2
   3 Date: 02-11-2009
   4 Author: Hermann Walth
   5 Topic: The Parser's Memory Leak
   6
   7 /----------------------\
   8 | 0. Table of Contents |
   9 \----------------------/
  10
  11 0. Table of Contents
  12 1. Introduction
  13 2. Problem and Possible Solution
  14 3. Addenda
  15
  16 /-----------------\
  17 | 1. Introduction |
  18 \-----------------/
  19
  20 So far, the parser practically contains no real code at all. However,
  21 its lexical analyzer already uses routines to allocate memory for whose
  22 deallocation the parser is responsible. Forgetting to implement these
  23 deallocation routines in the final parser would result in a fatal memory leak.
  24
  25 As the parser is not yet ready to deal with these deallocations, this document
  26 shall serve both as a reminder to implement these once the time is ready and
  27 as an instruction on how to deal with the upcoming problems.
  28
  29 /----------------------------------\
  30 | 2. Problem and Possible Solution |
  31 \----------------------------------/
  32
  33 The following enumerated statements will be used as examples throughout
  34 this text - in this case they will be referred to by their assigned number:
  35 S1: function ();
  36 S2: $variable1 = 3;
  37 S3: echo "Hello World";
  38 S4: $variable2 = "Hello World";
  39 S5: $variable3 = concatenate ($variable2, "!");
  40 S6: $variable4 = $variable3;
  41
  42 For now, only consider the statements 1 through 3. In each of these simple
  43 statements, the lexer allocates memory to tell the parser important
  44 information (stored in the shared variable `yylval`). In S1, it uses this
  45 memory to store the function's name, in S2 it stores the variable's name and
  46 in S3 it stores the string "Hello World" (beside the function name `echo`).
  47
  48 At a first glance, the solution seems to be both obvious and simple - which
  49 it is in the first two cases: Simply free the reserved memory after the parser
  50 has utilized the strings (i.e. looked up the respective function or variable).
  51
  52 One would tend to use the same method for S3. However, take a look at S4.
  53 Here, a string is assigned to a variable. Simple assignment and deallocation
  54 of the string would result in a variable whose content does not lie on
  55 allocated space.
  56 There are two relatively simple solutions to this problem:
  57 1. Either just don't deallocate strings in assignment statements
  58 2. Or assign a copy of the string to the variable to safely free the
  59    original string.
  60 Both of these solutions are perfectly functional, but the first one is
  61 definitely simpler and more efficient.
  62
  63 Concerning S4, one should also consider the possibility of $variable2 already
  64 containing a string. In this case, the parser also has to deallocate the
  65 former contents of $variable2 before assignment.
  66
  67 In order to return to the original problem, take a look at S5 and S6.
  68 In both statements string variables are used within expressions.
  69 Be aware that the parser does not memorize whether a value in an expression
  70 originated from a literal, a variable or an extended expression.
  71 Using the approach to tackle the problems aforementioned for statements 1
  72 through 3, the parser will thus try to deallocate the contents of $variable2
  73 after they have been passed to the function, making the variable useless.
  74 In S6, $variable3 is not endangered of being deallocated if solution 1 to
  75 the assignment problem is being used. However, $variable4 will be set to
  76 exactly the same string instead of to a copy of $variable3, which is probably
  77 not what is intended and may lead to unexpected behaviour.
  78
  79 A simple and workable - yet relatively inefficient - method to circumvent
  80 these problems would be to copy string variables whenever one is encountered
  81 within an expression. This will
  82 a) prevent string variables from being deallocated when used in an expression
  83 b) remove the danger of two variables sharing the same memory through
  84    assignments (the right-hand side in an assignment is always treated
  85    like an expression).
  86
  87 /------------\
  88 | 3. Addenda |
  89 \------------/
  90
  91 It was decided to copy string variables in expressions on 02-12-2009.
  92