From 14ebd5d58be3fcb5d2208f890498dd8c57f4d165 Mon Sep 17 00:00:00 2001 From: Robin Haberkorn Date: Tue, 17 Mar 2015 20:18:18 +0100 Subject: fixed invalid memory accesses in the expression stack and reworked expression stack this was probably a regression from d94b18819ad4ee3237c46ad43a962d0121f0c3fe and should not be in v0.5. The return value of Expressions::find_op() must always be checked since it might not find the operator, returning 0 (it used to be 0). A zero index pointed to uninitialized memory - in the worst case it pointed to invalid memory resulting in segfaults. Too large indices were also not handled. This was probably responsible for recent PPA build issues. Valgrind/memcheck reports this error but I misread it as a bogus warning. I took the opportunity to clean up the ValueStack implementation and made it more robust by adding a few assertions. ValueStacks now grow from large to small addresses (like stack data structures usually do). This means, there is no need to work with negative indices into the stack pointer. To reduce the potential for invalid stack accesses, stack indices are now unsigned and have origin 0. Previously, all indices < 1 were faulty but weren't checked. Also, I added some minor optimizations. --- src/expressions.cpp | 60 +++++++++++++------------------ src/expressions.h | 101 +++++++++++++++++++++++++++++++++------------------- src/parser.cpp | 16 ++++----- src/ring.cpp | 2 +- src/search.cpp | 2 +- 5 files changed, 98 insertions(+), 83 deletions(-) diff --git a/src/expressions.cpp b/src/expressions.cpp index fc1e5e2..8d21388 100644 --- a/src/expressions.cpp +++ b/src/expressions.cpp @@ -22,7 +22,6 @@ #include #include "sciteco.h" -#include "undo.h" #include "error.h" #include "expressions.h" @@ -30,20 +29,6 @@ namespace SciTECO { Expressions expressions; -void -Expressions::set_num_sign(gint sign) -{ - undo.push_var(num_sign); - num_sign = sign; -} - -void -Expressions::set_radix(gint r) -{ - undo.push_var(radix); - radix = r; -} - tecoInt Expressions::push(tecoInt number) { @@ -62,14 +47,14 @@ Expressions::push(tecoInt number) } tecoInt -Expressions::pop_num(int index) +Expressions::pop_num(guint index) { tecoInt n = 0; Operator op = pop_op(); g_assert(op == OP_NUMBER); - if (numbers.items() > 0) { + if (numbers.items()) { n = numbers.pop(index); numbers.undo_push(n, index); } @@ -78,7 +63,7 @@ Expressions::pop_num(int index) } tecoInt -Expressions::pop_num_calc(int index, tecoInt imply) +Expressions::pop_num_calc(guint index, tecoInt imply) { eval(); if (num_sign < 0) @@ -105,21 +90,21 @@ Expressions::push(Expressions::Operator op) Expressions::Operator Expressions::push_calc(Expressions::Operator op) { - int first = first_op(); + gint first = first_op(); /* calculate if op has lower precedence than op on stack */ - if (first && operators.peek(first) <= op) + if (first >= 0 && operators.peek(first) <= op) calc(); return push(op); } Expressions::Operator -Expressions::pop_op(int index) +Expressions::pop_op(guint index) { Operator op = OP_NIL; - if (operators.items() > 0) { + if (operators.items()) { op = operators.pop(index); operators.undo_push(op, index); } @@ -191,6 +176,9 @@ Expressions::eval(bool pop_brace) gint n = first_op(); Operator op; + if (n < 0) + break; + op = operators.peek(n); if (op == OP_LOOP) break; @@ -199,43 +187,43 @@ Expressions::eval(bool pop_brace) pop_op(n); break; } - if (n < 2) + if (n < 1) break; calc(); } } -int +guint Expressions::args(void) { - int n = 0; - int items = operators.items(); + guint n = 0; + guint items = operators.items(); - while (n < items && operators.peek(n+1) == OP_NUMBER) + while (n < items && operators.peek(n) == OP_NUMBER) n++; return n; } -int +gint Expressions::find_op(Operator op) { - int items = operators.items(); + guint items = operators.items(); - for (int i = 1; i <= items; i++) + for (guint i = 0; i < items; i++) if (operators.peek(i) == op) return i; - return 0; + return -1; /* not found */ } -int +gint Expressions::first_op(void) { - int items = operators.items(); + guint items = operators.items(); - for (int i = 1; i <= items; i++) { + for (guint i = 0; i < items; i++) { switch (operators.peek(i)) { case OP_NUMBER: case OP_NEW: @@ -245,14 +233,14 @@ Expressions::first_op(void) } } - return 0; + return -1; /* no operator */ } void Expressions::discard_args(void) { eval(); - for (int i = args(); i; i--) + for (guint i = args(); i; i--) pop_num_calc(); } diff --git a/src/expressions.h b/src/expressions.h index 5c2aa7e..a0e2908 100644 --- a/src/expressions.h +++ b/src/expressions.h @@ -28,14 +28,18 @@ namespace SciTECO { template class ValueStack { class UndoTokenPush : public UndoTokenWithSize { + /* + * FIXME: saving the UndoStack for each undo taken + * wastes a lot of memory + */ ValueStack *stack; Type value; - int index; + guint index; public: UndoTokenPush(ValueStack *_stack, - Type _value, int _index = 1) + Type _value, guint _index = 0) : stack(_stack), value(_value), index(_index) {} void @@ -48,10 +52,10 @@ class ValueStack { class UndoTokenPop : public UndoTokenWithSize { ValueStack *stack; - int index; + guint index; public: - UndoTokenPop(ValueStack *_stack, int _index = 1) + UndoTokenPop(ValueStack *_stack, guint _index = 0) : stack(_stack), index(_index) {} void @@ -61,15 +65,20 @@ class ValueStack { } }; - int size; - + /** Beginning of stack area */ Type *stack; - Type *top; + /** End of stack area */ + Type *stack_top; + + /** Pointer to top element on stack */ + Type *sp; public: - ValueStack(int _size = 1024) : size(_size) + ValueStack(gsize size = 1024) { - top = stack = new Type[size]; + stack = new Type[size]; + /* stack grows to smaller addresses */ + sp = stack_top = stack+size; } ~ValueStack() @@ -77,57 +86,67 @@ public: delete[] stack; } - inline int + inline guint items(void) { - return top - stack; + return stack_top - sp; } inline Type & - push(Type value, int index = 1) + push(Type value, guint index = 0) { - if (items() == size) + if (G_UNLIKELY(sp == stack)) throw Error("Stack overflow"); - for (int i = -index + 1; i; i++) - top[i+1] = top[i]; + /* reserve space for new element */ + sp--; + g_assert(items() > index); + + /* move away elements after index (index > 0) */ + for (guint i = 0; i < index; i++) + sp[i] = sp[i+1]; - top++; - return peek(index) = value; + return sp[index] = value; } inline void - undo_push(Type value, int index = 1) + undo_push(Type value, guint index = 0) { undo.push(new UndoTokenPush(this, value, index)); } inline Type - pop(int index = 1) + pop(guint index = 0) { + /* peek() already asserts */ Type v = peek(index); - top--; - while (--index) - top[-index] = top[-index + 1]; + /* elements after index are moved to index (index > 0) */ + while (index--) + sp[index+1] = sp[index]; + + /* free space of element to pop */ + sp++; return v; } inline void - undo_pop(int index = 1) + undo_pop(guint index = 0) { undo.push(new UndoTokenPop(this, index)); } inline Type & - peek(int index = 1) + peek(guint index = 0) { - return top[-index]; + g_assert(items() > index); + + return sp[index]; } inline void clear(void) { - top = stack; + sp = stack_top; } }; @@ -163,10 +182,18 @@ public: Expressions() : num_sign(1), radix(10) {} gint num_sign; - void set_num_sign(gint sign); + inline void + set_num_sign(gint sign) + { + undo.push_var(num_sign) = sign; + } gint radix; - void set_radix(gint r); + inline void + set_radix(gint r) + { + undo.push_var(radix) = r; + } tecoInt push(tecoInt number); @@ -183,14 +210,14 @@ public: } inline tecoInt - peek_num(int index = 1) + peek_num(guint index = 0) { return numbers.peek(index); } - tecoInt pop_num(int index = 1); - tecoInt pop_num_calc(int index, tecoInt imply); + tecoInt pop_num(guint index = 0); + tecoInt pop_num_calc(guint index, tecoInt imply); inline tecoInt - pop_num_calc(int index = 1) + pop_num_calc(guint index = 0) { return pop_num_calc(index, num_sign); } @@ -200,19 +227,19 @@ public: Operator push(Operator op); Operator push_calc(Operator op); inline Operator - peek_op(int index = 1) + peek_op(guint index = 0) { return operators.peek(index); } - Operator pop_op(int index = 1); + Operator pop_op(guint index = 0); void eval(bool pop_brace = false); - int args(void); + guint args(void); void discard_args(void); - int find_op(Operator op); + gint find_op(Operator op); inline void clear(void) @@ -226,7 +253,7 @@ public: private: void calc(void); - int first_op(void); + gint first_op(void); } expressions; } /* namespace SciTECO */ diff --git a/src/parser.cpp b/src/parser.cpp index 6ca6652..b16b792 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -898,7 +898,7 @@ StateStart::custom(gchar chr) BEGIN_EXEC(this); v = QRegisters::globals["_"]->get_integer(); - rc = expressions.pop_num_calc(1, v); + rc = expressions.pop_num_calc(0, v); if (eval_colon()) rc = ~rc; @@ -1086,7 +1086,7 @@ StateStart::custom(gchar chr) */ case 'J': BEGIN_EXEC(this); - v = expressions.pop_num_calc(1, 0); + v = expressions.pop_num_calc(0, 0); if (Validate::pos(v)) { if (current_doc_must_undo()) interface.undo_ssm(SCI_GOTOPOS, @@ -1888,7 +1888,7 @@ StateECommand::custom(gchar chr) expressions.push(Flags::ed); } else { tecoInt on = expressions.pop_num_calc(); - tecoInt off = expressions.pop_num_calc(1, ~(tecoInt)0); + tecoInt off = expressions.pop_num_calc(0, ~(tecoInt)0); undo.push_var(Flags::ed); Flags::ed = (Flags::ed & ~off) | on; @@ -2227,10 +2227,10 @@ cleanup: if (!expressions.args()) throw Error(" command requires at least a message code"); - scintilla_message.iMessage = expressions.pop_num_calc(1, 0); + scintilla_message.iMessage = expressions.pop_num_calc(0, 0); } if (!scintilla_message.wParam) - scintilla_message.wParam = expressions.pop_num_calc(1, 0); + scintilla_message.wParam = expressions.pop_num_calc(0, 0); return &States::scintilla_lparam; } @@ -2242,7 +2242,7 @@ StateScintilla_lParam::done(const gchar *str) if (!scintilla_message.lParam) scintilla_message.lParam = *str ? (sptr_t)str - : expressions.pop_num_calc(1, 0); + : expressions.pop_num_calc(0, 0); expressions.push(interface.ssm(scintilla_message.iMessage, scintilla_message.wParam, @@ -2288,7 +2288,7 @@ StateScintilla_lParam::done(const gchar *str) void StateInsert::initial(void) { - int args; + guint args; expressions.eval(); args = expressions.args(); @@ -2297,7 +2297,7 @@ StateInsert::initial(void) interface.ssm(SCI_BEGINUNDOACTION); for (int i = args; i > 0; i--) { - gchar chr = (gchar)expressions.peek_num(i); + gchar chr = (gchar)expressions.peek_num(i-1); interface.ssm(SCI_ADDTEXT, 1, (sptr_t)&chr); } for (int i = args; i > 0; i--) diff --git a/src/ring.cpp b/src/ring.cpp index c3fec3f..f944e40 100644 --- a/src/ring.cpp +++ b/src/ring.cpp @@ -337,7 +337,7 @@ StateEditFile::do_edit(tecoInt id) void StateEditFile::initial(void) { - tecoInt id = expressions.pop_num_calc(1, -1); + tecoInt id = expressions.pop_num_calc(0, -1); allowFilename = true; diff --git a/src/search.cpp b/src/search.cpp index 370dbfc..8013385 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -527,7 +527,7 @@ StateSearch::done(const gchar *str) if (eval_colon()) expressions.push(search_reg->get_integer()); else if (IS_FAILURE(search_reg->get_integer()) && - !expressions.find_op(Expressions::OP_LOOP) /* not in loop */) + expressions.find_op(Expressions::OP_LOOP) < 0 /* not in loop */) interface.msg(InterfaceCurrent::MSG_ERROR, "Search string not found!"); return &States::start; -- cgit v1.2.3