diff options
Diffstat (limited to 'system/kernel')
| -rw-r--r-- | system/kernel/CONTENTS | 7 | ||||
| -rw-r--r-- | system/kernel/Makefile | 16 | ||||
| -rw-r--r-- | system/kernel/pdp_debug.c | 21 | ||||
| -rw-r--r-- | system/kernel/pdp_dpd_command.c | 87 | ||||
| -rw-r--r-- | system/kernel/pdp_list.c | 931 | ||||
| -rw-r--r-- | system/kernel/pdp_mem.c | 129 | ||||
| -rw-r--r-- | system/kernel/pdp_packet.c | 634 | ||||
| -rw-r--r-- | system/kernel/pdp_packet2.c | 623 | ||||
| -rw-r--r-- | system/kernel/pdp_post.c | 48 | ||||
| -rw-r--r-- | system/kernel/pdp_symbol.c | 196 | ||||
| -rw-r--r-- | system/kernel/pdp_type.c | 473 |
11 files changed, 3165 insertions, 0 deletions
diff --git a/system/kernel/CONTENTS b/system/kernel/CONTENTS new file mode 100644 index 0000000..c2f7c8c --- /dev/null +++ b/system/kernel/CONTENTS @@ -0,0 +1,7 @@ +debug debug stuff +forth the forth system +list the list implementation +mem memory allocation stuf +packet the packet memory manager +type the type handling and conversion system +symbol symbol implementation, with namespaces for forth, types, classes, ... diff --git a/system/kernel/Makefile b/system/kernel/Makefile new file mode 100644 index 0000000..08b21cd --- /dev/null +++ b/system/kernel/Makefile @@ -0,0 +1,16 @@ + +OBJECTS = pdp_packet.o pdp_type.o pdp_dpd_command.o \ + pdp_list.o pdp_debug.o pdp_symbol.o \ + pdp_mem.o pdp_post.o + + +include ../../Makefile.config + +all: pdp_main_clean $(OBJECTS) + +pdp_main_clean: + rm -f pdp.o + +clean: + rm -f *~ + rm -f *.o diff --git a/system/kernel/pdp_debug.c b/system/kernel/pdp_debug.c new file mode 100644 index 0000000..07f6541 --- /dev/null +++ b/system/kernel/pdp_debug.c @@ -0,0 +1,21 @@ +#include <sys/types.h> +#include <signal.h> +#include <unistd.h> +#include "pdp_post.h" + +int pdp_debug_sigtrap_on_assert; + + +void pdp_assert_hook (char *condition, char *file, int line) +{ + pdp_post("PDP_ASSERT (%s) failed in file %s, line %u. ", condition, file, line); + pdp_post("%s.\n", pdp_debug_sigtrap_on_assert ? "sending SIGTRAP" : "continuing"); + + if (pdp_debug_sigtrap_on_assert) kill(getpid(), SIGTRAP); +} + + +void pdp_debug_setup(void) +{ + pdp_debug_sigtrap_on_assert = 1; +} diff --git a/system/kernel/pdp_dpd_command.c b/system/kernel/pdp_dpd_command.c new file mode 100644 index 0000000..d812cf2 --- /dev/null +++ b/system/kernel/pdp_dpd_command.c @@ -0,0 +1,87 @@ + +/* + * Pure Data Packet header file. DPD command class + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + +/* this object implements a dpd command queue and command object */ + +#include "pdp_dpd_command.h" +#include "pdp_mem.h" + +void pdp_dpd_commandfactory_init(t_pdp_dpd_commandfactory *x, u32 size) +{ + x->nb_commands = 0; + x->command_size = size; + x->command = 0; +} + +void _pdp_dpd_commandfactory_free(t_pdp_dpd_command *x) +{ + if (x) _pdp_dpd_commandfactory_free(x->next); + pdp_dealloc(x); +} + +void pdp_dpd_commandfactory_free(t_pdp_dpd_commandfactory *x) +{ + _pdp_dpd_commandfactory_free(x->command); + x->command = 0; + x->nb_commands = 0; +} + + +/* factory method */ +t_pdp_dpd_command *pdp_dpd_commandfactory_get_new_command(t_pdp_dpd_commandfactory *x) +{ + + t_pdp_dpd_command *c = x->command; + t_pdp_dpd_command *oldhead = c; + + /* check if we can reuse */ + while (c){ + if (!c->used){ + c->used = 1; + //post("reusing command %x", c, c->used); + return c; + } + //post("command %x is used %d", c, c->used); + c = c->next; + } + + /* create a new command */ + x->command = (t_pdp_dpd_command *)pdp_alloc(x->command_size); + x->command->next = oldhead; + x->command->used = 1; + x->nb_commands++; + //post("created command %x, nbcommands: %d", x->command, x->nb_commands); + return x->command; + +} + + +/* (self)destructor */ +void pdp_dpd_command_suicide(void *x) +{ + t_pdp_dpd_command *c = (t_pdp_dpd_command *)x; + c->used = 0; + //post("command %x committed suicide %d", c, c->used); +} + + + + diff --git a/system/kernel/pdp_list.c b/system/kernel/pdp_list.c new file mode 100644 index 0000000..deeb7f1 --- /dev/null +++ b/system/kernel/pdp_list.c @@ -0,0 +1,931 @@ + +/* + * Pure Data Packet header file. List class + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + +/* who can live without a list, hmm? + + this is sorth of a compromise between lists, queues, + stacks, lisp and forth. list contain pdp atoms + (floats, ints, symbols, pointers, packets or lists) */ + + +#include <pthread.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include "pdp_list.h" +#include "pdp_symbol.h" +#include "pdp_packet.h" +#include "pdp_type.h" +#include "pdp_types.h" +#include "pdp_mem.h" +#include "pdp_post.h" +#include "pdp_debug.h" + +#define D if (0) + + +t_pdp_fastalloc *_fast_atom_allocator; +t_pdp_fastalloc *_fast_list_allocator; + + + + +static void _pdp_list_dealloc(t_pdp_list *l) +{ + pdp_fastalloc_save_atom(_fast_list_allocator, l); +} + +// allocator macros +#define PDP_ATOM_ALLOC() pdp_fastalloc_new_atom(_fast_atom_allocator) +#define PDP_ATOM_DEALLOC(x) pdp_fastalloc_save_atom(_fast_atom_allocator, x) +#define PDP_LIST_ALLOC() pdp_fastalloc_new_atom(_fast_list_allocator) +#define PDP_LIST_DEALLOC(x) _pdp_list_dealloc(x) +//#define PDP_LIST_DEALLOC(x) pdp_fastalloc_save_atom(_fast_list_allocator, x) + + + + +/* some private helper methods */ + +/* list pool setup */ +void pdp_list_setup(void) +{ + + + + /* create fast allocators */ + _fast_atom_allocator = pdp_fastalloc_new(sizeof(t_pdp_atom)); + _fast_list_allocator = pdp_fastalloc_new(sizeof(t_pdp_list)); + + /* testing code */ + if (0){ + char *next; + t_pdp_list *l = pdp_tree_from_cstring("( een twee (3 vier ()) vijf (6.0)", &next); + if (!l){ + pdp_post("parse error:"); + pdp_post(next); + } + else{ + pdp_list_print(l); + } + exit(1); + } + + +} + + + +/* create a list */ +t_pdp_list* pdp_list_new(int elements) +{ + t_pdp_atom *a = 0; + t_pdp_list *l = PDP_LIST_ALLOC(); + l->elements = 0; + + + if (elements){ + a = PDP_ATOM_ALLOC(); + l->elements++; + a->t = a_undef; + a->w.w_int = 0; + a->next = 0; + elements--; + } + l->first = a; + l->last = a; + + while (elements--){ + a = PDP_ATOM_ALLOC(); + l->elements++; + a->t = a_undef; + a->w.w_int = 0; + a->next = l->first; + l->first = a; + } + + return l; +} + +/* clear a list */ +void pdp_list_clear(t_pdp_list *l) +{ + t_pdp_atom *a = l->first; + t_pdp_atom *next_a; + + while(a){ + next_a = a->next; + PDP_ATOM_DEALLOC(a); + a = next_a; + } + + l->first = 0; + l->last = 0; + l->elements = 0; + +} + +/* destroy a list */ +void pdp_list_free(t_pdp_list *l) +{ + if (l){ + pdp_list_clear(l); + PDP_LIST_DEALLOC(l); + } +} + + +/* destroy a (sub)tree */ +void pdp_tree_free(t_pdp_list *l) +{ + if (l) { + pdp_tree_clear(l); + PDP_LIST_DEALLOC(l); + } +} + +/* clear a tree */ +void pdp_tree_clear(t_pdp_list *l) +{ + t_pdp_atom *a = l->first; + t_pdp_atom *next_a; + + + while(a){ + if (a->t == a_list){ + pdp_tree_free(a->w.w_list); + } + next_a = a->next; + PDP_ATOM_DEALLOC(a); + a = next_a; + } + + l->first = 0; + l->last = 0; + l->elements = 0; + +} + +/* BEGIN PARSER CODE */ + +/* real whitespace handling */ +static inline int _is_whitespace(char c){return (c == ' ' || c == '\n' || c == '\t');} +static inline void _skip_real_whitespace(char **c){while (_is_whitespace(**c)) (*c)++;} + +/* comment handling */ +static inline int _is_left_comment(char c) {return (c == '#');} +static inline int _is_right_comment(char c) {return (c == '\n');} +static inline void _skip_comment(char **c) +{ + if (!_is_left_comment(**c)) return; + (*c)++; + while (!_is_right_comment(**c)){ + if (!**c) return; // no terminating newline + (*c)++; + } + (*c)++; +} + +/* comment + whitespace handling */ +static inline void _skip_whitespace(char **c) +{ + char *prev_c; + /* skip comments and whitespace until the + pointer stops moving */ + do { + prev_c = *c; + _skip_real_whitespace(c); + _skip_comment(c); + } while (prev_c != *c); +} + +static inline int _is_left_separator(char c) {return (c == '(');} +static inline int _is_right_separator(char c) {return (c == ')');} +static inline int _is_terminator(char c) {return (c == 0);} + +/* the end of an atom is marked by a separator */ +static inline int _is_separator(char c) {return (_is_terminator(c) + || _is_left_separator(c) + || _is_right_separator(c) + || _is_whitespace(c));} + + +/* parse a single pure atom from a zero terminated string + a pure atom is either a number (int or float) xor a symbol +*/ + +static inline void _parse_pure_atom(t_pdp_atom *a, char *c) +{ + char *next; + + /* check if the string has a decimal point */ + int has_decimal = 0; + char *c2; + for(c2 = c; *c2; c2++){ + if (*c2 == '.') { has_decimal = 1; break; } + } + + /* try parsing as a number (int or float) first */ + if (has_decimal){ // try float + float f = strtod(c, &next); + if (next[0] == 0){ // got everything? + D pdp_post("parsing float %f", f); + a->t = a_float; + a->w = (t_pdp_word)f; + return; + } + } + else { // try int + int i = strtol(c, &next, 0); + if (next[0] == 0){ // got everything? + D pdp_post("parsing int %d", i); + a->t = a_int; + a->w = (t_pdp_word)i; + return; + } + } + + + /* number parsing failed: it's a symbol */ + D pdp_post("parsing symbol %s", c); + a->t = a_symbol; + a->w = (t_pdp_word)pdp_gensym(c); + +} + +t_pdp_atom *pdp_atom_new(void){t_pdp_atom *a = PDP_ATOM_ALLOC(); a->next = 0; return a;} +void pdp_atom_free(t_pdp_atom *a){PDP_ATOM_DEALLOC(a);} + +/* there are two parser methods: parse an atom and parse a list + both can call each other recursively. + the atoms and list are allocated with pdp_list_new and + pdp_atom_new respectively */ + +t_pdp_atom *pdp_atom_from_cstring(char *chardef, char **next) +{ + t_pdp_atom *a = 0; + + /* skip whitespace and check if there's anything left */ + _skip_whitespace(&chardef); + if (!chardef[0] || _is_right_separator(*chardef)) goto done; + + + /* check if it's a list atom */ + if(_is_left_separator(*chardef)){ + t_pdp_list *l = pdp_tree_from_cstring(chardef, &chardef); + if (l){ + a = pdp_atom_new(); + a->t = a_list; + a->w.w_list = l; + } + + } + + /* we have a pure atom, copy it to a temp buffer */ + else{ + int n = 0; + while (!_is_separator(chardef[n])) n++; + if (!n) goto done; + else { + char tmp[n+1]; + strncpy(tmp, chardef, n); + tmp[n] = 0; + a = pdp_atom_new(); + _parse_pure_atom(a, tmp); + chardef += n; + } + + } + + done: + if (next) *next = chardef; + return a; + +} + +/* check if a tree (list of lists) matches a certain type syntax + types: + + symbol -> a_sym; + int -> a_int; + float -> a_float; + packet -> a_packet; + list -> a_list; + ... -> zero or more times the preceeding elements in the list +*/ + + + +/* create a list from a character string */ +t_pdp_list *pdp_tree_from_cstring(char *chardef, char **next) +{ + t_pdp_list *l = pdp_list_new(0); + t_pdp_atom *a = 0; + + D pdp_post ("creating list from char: %s", chardef); + + /* find opening parenthesis and skip it*/ + _skip_whitespace(&chardef); + if (!_is_left_separator(*chardef)) goto error; else chardef++; + + /* chardef now points at the first atom, start adding atoms */ + while(1){ + a = pdp_atom_from_cstring(chardef, &chardef); + if (a)pdp_list_add_back_atom(l, a); + else break; + } + + /* skip whitespace and find closing parenthesis */ + _skip_whitespace(&chardef); + if (!_is_right_separator(*chardef)) goto error; else chardef++; + if (next) *next = chardef; + return l; + + error: + /* end of string encountered: parse error */ + D pdp_post("parse error: %s", chardef); + if (next) *next = chardef; + pdp_tree_free(l); //this will free all sublists too + return 0; // parse error + + + +} + +/* END PARSER CODE */ + +// this assumes syntax's syntax is correct +int pdp_tree_check_syntax(t_pdp_list *list, t_pdp_list *syntax) +{ + + t_pdp_atom *la = 0; + t_pdp_atom *sa = 0; + + t_pdp_symbol *ellipsis = pdp_gensym("..."); + t_pdp_symbol *wildcard = pdp_gensym("*"); + + /* handle empty lists */ + if (list->elements == 0){ + + /* check if syntax list is empty */ + if (syntax->elements == 0) goto match; + + /* check if syntax list has ellipsis */ + if (syntax->last->t == a_symbol && + syntax->last->w.w_symbol == ellipsis) goto match; + + /* default: no match */ + goto nomatch; + } + + + /* loop over list and syntax list */ + for (la = list->first, sa = syntax->first; + la && sa; + la = la->next, sa = sa->next){ + + D pdp_post("pdp_tree_check_syntax: starting check"); + + checkatom: + /* what do we expect for this atom ? */ + switch(sa->t){ + case a_list: + D pdp_post("expecting list"); + /* we need to recurse down the tree */ + /* exit if the current list to check + does not have a sublist */ + if (la->t != a_list) { + D pdp_post("not a list"); + goto nomatch; + } + + /* recurse and exit if no match */ + D pdp_post("checking sublist"); + if (!pdp_tree_check_syntax(la->w.w_list, sa->w.w_list)){ + D pdp_post("sublist does not match"); + goto nomatch; + } + + break; + + case a_symbol: + + /* if ellipsis, rewind */ + if (ellipsis == sa->w.w_symbol){ + D pdp_post("got ellipsis"); + /* check if we're not looping */ + if (sa == syntax->first){ + D pdp_post("ellipsis at start of list"); + goto nomatch; + } + /* try again */ + sa = syntax->first; + D pdp_post("ellipsis rewind"); + goto checkatom; + } + + else if (wildcard == sa->w.w_symbol){ + D pdp_post("got wildcard"); + } + + /* ordinary atom: check type */ + else{ + D pdp_post("expecting %s", sa->w.w_symbol->s_name); + switch(la->t){ + + case a_int: + if (sa->w.w_symbol != pdp_gensym("int")) goto nomatch; break; + case a_float: + if (sa->w.w_symbol != pdp_gensym("float")) goto nomatch; break; + case a_symbol: + if (sa->w.w_symbol != pdp_gensym("symbol")) goto nomatch; break; + case a_packet: + if (sa->w.w_symbol != pdp_gensym("packet")) goto nomatch; break; + case a_list: + if (sa->w.w_symbol != pdp_gensym("list")) goto nomatch; break; + + default: + goto nomatch; + } + D pdp_post("OK"); + } + + break; + + default: + D pdp_post("syntax syntax error"); + pdp_list_print(syntax); + goto nomatch; // incorrect syntax description + } + + } + + /* loop ended because one of the lists was finished */ + /* only two cases can be valid: la == 0 and (sa == 0 or ellipsis) */ + + if (la != 0){ + D pdp_post("not end of list -> no match"); + goto nomatch; + } + + if (sa == 0) goto match; + + if (!(sa->t == a_symbol && sa->w.w_symbol == ellipsis)){ + D pdp_post("syntax list not in ellipsis position -> no match"); + goto nomatch; + } + + + /* exits */ + match: + D pdp_post("pdp_tree_check_syntax: match"); + return 1; + nomatch: + D pdp_post("pdp_tree_check_syntax: no match"); + return 0; + +} + + + +/* traversal */ +void pdp_list_apply(t_pdp_list *l, t_pdp_atom_method m) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next) m(a); +} + +void pdp_tree_apply(t_pdp_list *l, t_pdp_atom_method m) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next){ + if (a->t == a_list) pdp_tree_apply(a->w.w_list, m); + else m(a); + } +} + +void pdp_list_apply_word_method(t_pdp_list *l, + t_pdp_word_type type, t_pdp_word_method wm) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next){ + if (a->t == type) wm(a->w); + } +} +void pdp_list_apply_pword_method(t_pdp_list *l, + t_pdp_word_type type, t_pdp_pword_method pwm) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next){ + if (a->t == type) pwm(&a->w); + } +} + +void pdp_tree_apply_word_method(t_pdp_list *l, + t_pdp_word_type type, t_pdp_word_method wm) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next){ + if (a->t == a_list) pdp_tree_apply_word_method(a->w.w_list, type, wm); + else if (a->t == type) wm(a->w); + } +} +void pdp_tree_apply_pword_method(t_pdp_list *l, + t_pdp_word_type type, t_pdp_pword_method pwm) +{ + t_pdp_atom *a; + if (!l) return; + for (a=l->first; a; a=a->next){ + if (a->t == a_list) pdp_tree_apply_pword_method(a->w.w_list, type ,pwm); + else if (a->t == type) pwm(&a->w); + } +} + +static void _atom_packet_mark_unused(t_pdp_atom *a) +{ + if (a->t == a_packet){ + pdp_packet_mark_unused(a->w.w_packet); + a->w.w_packet = -1; + } +} + +static void _atom_packet_copy_ro(t_pdp_atom *a) +{ + int p; + if (a->t == a_packet){ + a->w.w_packet = pdp_packet_copy_ro(a->w.w_packet); + } +} + +void pdp_tree_strip_packets (t_pdp_list *l) +{ + pdp_tree_apply(l, _atom_packet_mark_unused); +} + +static void _pdp_tree_copy_ro_packets (t_pdp_list *l) +{ + pdp_tree_apply(l, _atom_packet_copy_ro); +} + +t_pdp_list *pdp_tree_copy_ro(t_pdp_list *l) +{ + t_pdp_list *l2 = pdp_tree_copy(l); + _pdp_tree_copy_ro_packets(l2); + return l2; +} + +static void _pdp_atomlist_fprint(FILE* f, t_pdp_atom *a); + +static void _pdp_atom_fprint(FILE* f, t_pdp_atom *a) +{ + if (!a){ + fprintf(f, "<NULL ATOM>"); + return; + } + + switch(a->t){ + /* generic atoms */ + case a_symbol: fprintf(f, "%s",a->w.w_symbol->s_name); break; + case a_float: fprintf(f, "%f",a->w.w_float); break; + case a_int: fprintf(f, "%d",a->w.w_int); break; + case a_packet: fprintf(f, "#<pdp %d %s>",a->w.w_packet, + pdp_packet_get_description(a->w.w_packet)->s_name); break; + case a_pointer: fprintf(f, "#<0x%08x>", a->w.w_int); break; + case a_list: _pdp_atomlist_fprint(f, a->w.w_list->first); break; + case a_atom_pointer: + fprintf(f, "->"); + _pdp_atom_fprint(f, a->w.w_atom_pointer); + break; + case a_undef: fprintf(f, "<undef>"); break; + + /* forth atoms */ + case a_forthword: fprintf(f, "#<forth word 0x%08x>", a->w.w_int); break; + case a_vmword: fprintf(f, "#<vm word 0x%08x>", a->w.w_int); break; + case a_vmmacro: fprintf(f, "#<vm macro 0x%08x>", a->w.w_int); break; + + + default: fprintf(f, "<unknown type>"); break; + } +} + +/* debug */ +static void _pdp_atomlist_fprint(FILE* f, t_pdp_atom *a) +{ + fprintf(f, "("); + while (a){ + _pdp_atom_fprint(f,a); + a = a->next; + if (a) fprintf(f, " "); + } + fprintf(f, ")"); +} + +void _pdp_list_fprint(FILE* f, t_pdp_list *l) +{ + _pdp_atomlist_fprint(f, l->first); + fprintf(f, "\n"); +} + +void pdp_list_print(t_pdp_list *l) +{ + _pdp_list_fprint(stderr, l); +} + +void pdp_atom_print(t_pdp_atom *a) +{ + _pdp_atom_fprint(stderr, a); +} + +/* public list operations */ + + + + +/* add a atom/word to the start of the list */ +void pdp_list_add_atom(t_pdp_list *l, t_pdp_atom *a) +{ + a->next = l->first; + l->first = a; + l->elements++; + if (!l->last) l->last = a; +} + +void pdp_list_add(t_pdp_list *l, t_pdp_word_type t, t_pdp_word w) +{ + t_pdp_atom *a = PDP_ATOM_ALLOC(); + a->t = t; + a->w = w; + pdp_list_add_atom(l, a); +} + + +/* add a word to the end of the list */ +void pdp_list_add_back_atom(t_pdp_list *l, t_pdp_atom *a) +{ + + l->elements++; + a->next = 0; + if (l->last){ + l->last->next = a; + } + else{ + l->first = a; + } + l->last = a; +} + +void pdp_list_add_back(t_pdp_list *l, t_pdp_word_type t, t_pdp_word w) +{ + t_pdp_atom *a = PDP_ATOM_ALLOC(); + a->w = w; + a->t = t; + pdp_list_add_back_atom(l, a); +} + +/* get list size */ +int pdp_list_size(t_pdp_list *l) +{ + return l->elements; +} + + + + +/* pop: return first item and remove */ +t_pdp_atom *pdp_list_pop_atom(t_pdp_list *l) +{ + t_pdp_atom *a = l->first; + if (!a) return a; + + l->first = a->next; + l->elements--; + if (!l->first) l->last = 0; + a->next = 0; // detach + return a; +} + + +/* pop: return first item and remove */ +t_pdp_word pdp_list_pop(t_pdp_list *l) +{ + t_pdp_atom *a = pdp_list_pop_atom(l); + t_pdp_word w=a->w; + PDP_ATOM_DEALLOC(a); + return w; +} + + + + +/* pop from one list and push to other */ +void pdp_list_pop_push(t_pdp_list *source, t_pdp_list *dest) +{ + t_pdp_atom *a = source->first; + + /* pop atom */ + if (--(source->elements)){source->last = 0;} + source->first = a->next; + + /* push atom */ + a->next = dest->first; + if (dest->elements++) {dest->last = a;} + dest->first = a; + + return; + +} + + +/* return element at index */ +t_pdp_word pdp_list_index(t_pdp_list *l, int index) +{ + t_pdp_atom *a; + for (a = l->first; index--; a = a->next); + return a->w; +} + + + + + +/* remove an element from a list */ +void pdp_list_remove(t_pdp_list *l, t_pdp_word_type t, t_pdp_word w) +{ + t_pdp_atom head; + t_pdp_atom *a; + t_pdp_atom *kill_a; + head.next = l->first; + + for(a = &head; a->next; a = a->next){ + if (a->next->w.w_int == w.w_int && a->next->t == t){ + kill_a = a->next; // element to be killed + a->next = a->next->next; // remove link + PDP_ATOM_DEALLOC(kill_a); + l->elements--; + l->first = head.next; // restore the start pointer + if (l->last == kill_a) { // restore the end pointer + l->last = (a != &head) ? a : 0; + } + + break; + } + } + +} + + + + + +/* copy a list */ +t_pdp_list* pdp_tree_copy_reverse(t_pdp_list *list) +{ + t_pdp_list *newlist = pdp_list_new(0); + t_pdp_atom *a; + for (a = list->first; a; a = a->next) + if (a->t == a_list){ + pdp_list_add(newlist, a->t, + (t_pdp_word)pdp_tree_copy_reverse(a->w.w_list)); + } + else{ + pdp_list_add(newlist, a->t, a->w); + } + return newlist; +} +t_pdp_list* pdp_list_copy_reverse(t_pdp_list *list) +{ + t_pdp_list *newlist = pdp_list_new(0); + t_pdp_atom *a; + for (a = list->first; a; a = a->next) + pdp_list_add(newlist, a->t, a->w); + return newlist; +} + +t_pdp_list* pdp_tree_copy(t_pdp_list *list) +{ + t_pdp_list *newlist = pdp_list_new(list->elements); + t_pdp_atom *a_src = list->first; + t_pdp_atom *a_dst = newlist->first; + + while(a_src){ + a_dst->t = a_src->t; + if (a_dst->t == a_list){ //recursively copy sublists (tree copy) + a_dst->w.w_list = pdp_tree_copy(a_src->w.w_list); + } + else{ + a_dst->w = a_src->w; + } + a_src = a_src->next; + a_dst = a_dst->next; + } + + return newlist; +} +t_pdp_list* pdp_list_copy(t_pdp_list *list) +{ + t_pdp_list *newlist = pdp_list_new(list->elements); + t_pdp_atom *a_src = list->first; + t_pdp_atom *a_dst = newlist->first; + + while(a_src){ + a_dst->t = a_src->t; + a_dst->w = a_src->w; + a_src = a_src->next; + a_dst = a_dst->next; + } + return newlist; +} + +void pdp_list_join (t_pdp_list *l, t_pdp_list *tail) +{ + if (tail->elements){ + l->elements += tail->elements; + if (l->last){ + l->last->next = tail->first; + l->last = tail->last; + } + else { + l->first = tail->first; + l->last = tail->last; + } + } + PDP_LIST_DEALLOC(tail); //delete the tail header +} + +void pdp_list_cat (t_pdp_list *l, t_pdp_list *tail) +{ + t_pdp_list *tmp = pdp_list_copy(tail); + pdp_list_join(l, tmp); +} + + +/* in place reverse: atoms stay the same + they are just relinked. so pointers will stay accurate */ +void pdp_list_reverse(t_pdp_list *l) +{ + t_pdp_list tmp; + t_pdp_atom *a; + tmp.first = l->first; + tmp.last = l->last; + tmp.elements = l->elements; + l->first = 0; + l->last = 0; + l->elements = 0; + while (a = pdp_list_pop_atom(&tmp)){ + pdp_list_add_atom(l, a); + } +} + +void pdp_list_reverse_old(t_pdp_list *l) +{ + t_pdp_list *l2 = pdp_list_copy_reverse(l); + pdp_list_clear(l); + l->first = l2->first; + l->last = l2->last; + l->elements = l2->elements; + _pdp_list_dealloc(l2); +} + +/* check if a list contains an element */ +int pdp_list_contains(t_pdp_list *list, t_pdp_word_type t, t_pdp_word w) +{ + t_pdp_atom *a; + for(a = list->first; a; a=a->next){ + if (a->w.w_int == w.w_int && a->t == t) return 1; + } + return 0; +} + +/* add a thing to the start of the list if it's not in there already */ +void pdp_list_add_to_set(t_pdp_list *list, t_pdp_word_type t, t_pdp_word w) +{ + if (!pdp_list_contains(list, t, w)) + pdp_list_add(list, t, w); +} + + + + diff --git a/system/kernel/pdp_mem.c b/system/kernel/pdp_mem.c new file mode 100644 index 0000000..33822ef --- /dev/null +++ b/system/kernel/pdp_mem.c @@ -0,0 +1,129 @@ +/* + * Pure Data Packet system file: memory allocation + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + +#include <stdlib.h> +#include "pdp_mem.h" +#include "pdp_debug.h" + + +/* malloc wrapper that calls garbage collector */ +void *pdp_alloc(int size) +{ + void *ptr = malloc(size); + + PDP_ASSERT(ptr); + + return ptr; + + //TODO: REPAIR THIS + //post ("malloc failed in a pdp module: running garbage collector."); + //pdp_pool_collect_garbage(); + //return malloc(size); +} + + +void pdp_dealloc(void *stuff) +{ + free (stuff); +} + + +/* fast atom allocation object + well, this is not too fast yet, but will be later + when it suports linux futexes or atomic operations */ + +//#include <pthread.h> + +/* private linked list struct */ +typedef struct _fastalloc +{ + struct _fastalloc * next; +} t_fastalloc; + + + + +static void _pdp_fastalloc_lock(t_pdp_fastalloc *x){pthread_mutex_lock(&x->mut);} +static void _pdp_fastalloc_unlock(t_pdp_fastalloc *x){pthread_mutex_unlock(&x->mut);} + +static void _pdp_fastalloc_refill_freelist(t_pdp_fastalloc *x) +{ + t_fastalloc *atom; + unsigned int i; + + PDP_ASSERT(x->freelist == 0); + + /* get a new block + there is no means of freeing the data afterwards, + this is a fast implementation with the tradeoff of data + fragmentation "memory leaks".. */ + + x->freelist = pdp_alloc(x->block_elements * x->atom_size); + + /* link all atoms together */ + atom = x->freelist; + for (i=0; i<x->block_elements-1; i++){ + atom->next = (t_fastalloc *)(((char *)atom) + x->atom_size); + atom = atom->next; + } + atom->next = 0; + +} + +void *pdp_fastalloc_new_atom(t_pdp_fastalloc *x) +{ + t_fastalloc *atom; + + _pdp_fastalloc_lock(x); + + /* get an atom from the freelist + or refill it and try again */ + while (!(atom = x->freelist)){ + _pdp_fastalloc_refill_freelist(x); + } + + /* delete the element from the freelist */ + x->freelist = x->freelist->next; + atom->next = 0; + + _pdp_fastalloc_unlock(x); + + return (void *)atom; + +} +void pdp_fastalloc_save_atom(t_pdp_fastalloc *x, void *atom) +{ + _pdp_fastalloc_lock(x); + ((t_fastalloc *)atom)->next = x->freelist; + x->freelist = (t_fastalloc *)atom; + _pdp_fastalloc_unlock(x); +} + +t_pdp_fastalloc *pdp_fastalloc_new(unsigned int size) +{ + t_pdp_fastalloc *x = pdp_alloc(sizeof(*x)); + if (size < sizeof(t_fastalloc)) size = sizeof(t_fastalloc); + x->freelist = 0; + x->atom_size = size; + x->block_elements = PDP_FASTALLOC_BLOCK_ELEMENTS; + pthread_mutex_init(&x->mut, NULL); + return x; +} + diff --git a/system/kernel/pdp_packet.c b/system/kernel/pdp_packet.c new file mode 100644 index 0000000..0eb569a --- /dev/null +++ b/system/kernel/pdp_packet.c @@ -0,0 +1,634 @@ +/* + * Pure Data Packet system implementation: Packet Manager + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + + + +#include <stdio.h> +#include <pthread.h> +#include <unistd.h> +#include <string.h> +#include "pdp_post.h" +#include "pdp_packet.h" +#include "pdp_mem.h" +#include "pdp_list.h" +#include "pdp_type.h" +#include "pdp_debug.h" + + +/* packet implementation. contains class and packet (instance) handling + + some notes on packet operations. + copy ro/rw and unregister are relatively straightforward + packet creation can be done in 2 ways in this interface: + create + reuse + however, these methods should only be called by specific factory + methods, so the user should only create packets using pdp_factory_newpacket + + reuse or create is thus the responsability of the factory methods for + each packet type (class) implementation + + +*/ + + +/* NOTE: + the packet pool methods are called within the pool locks. this probably + needs to change, because it will cause deadlocks for container packets (fobs) */ + + +/* new implementation: probably just a minor adjustment: add the reuse fifo attached + to type desc symbol name + need to check and possibly eliminate hacks for non-pure packets + + pdp_packet_new: + LOCK + 1. check reuse fifo + 2. empty -> create packet+return (search array) + 3. element -> check if type is correct, yes->pop+return, no->goto 1. + UNLOCK + 4. wakeup + + pdp_packet_mark_unused + + 1. check refcount. if > 1 dec + exit + 2. if 1 put packet to sleep + 3. dec refcount + 4. add to reuse fifo (no fifo -> create) + + pdp_packet_delete: analogous to mark_unused + pdp_packet_copy_ro/rw: analogous to new + +*/ + + +/* the pool */ +#define PDP_INITIAL_POOL_SIZE 64 +static int pdp_pool_size; +static t_pdp** pdp_pool; + +/* mutex: protects the pool and reuse lists attached to symbols */ +static pthread_mutex_t pdp_pool_mutex; +#define LOCK pthread_mutex_lock (&pdp_pool_mutex) +#define UNLOCK pthread_mutex_unlock (&pdp_pool_mutex) + +/* the list of classes */ +static t_pdp_list *class_list; + +/* debug */ +void +pdp_packet_print_debug(int packet) +{ + t_pdp *h = pdp_packet_header(packet); + pdp_post("debug info for packet %d", packet); + if (!h){ + pdp_post("invalid packet"); + } + else{ + pdp_post ("\ttype: %d", h->type); + pdp_post ("\tdesc: %s", h->desc ? h->desc->s_name : "unknown"); + pdp_post ("\tsize: %d", h->size); + pdp_post ("\tflags: %x", h->flags); + pdp_post ("\tusers: %d", h->users); + pdp_post ("\tclass: %x", h->theclass); + } +} + + + +/* setup methods */ + +void +pdp_packet_setup(void) +{ + + pdp_pool_size = PDP_INITIAL_POOL_SIZE; + pdp_pool = (t_pdp **)pdp_alloc(PDP_INITIAL_POOL_SIZE * sizeof(t_pdp *)); + bzero(pdp_pool, pdp_pool_size * sizeof(t_pdp *)); + class_list = pdp_list_new(0); + pthread_mutex_init(&pdp_pool_mutex, NULL); +} + +/* class methods */ +t_pdp_class *pdp_class_new(t_pdp_symbol *type, t_pdp_factory_method create){ + t_pdp_class *c = (t_pdp_class *)pdp_alloc(sizeof(t_pdp_class)); + memset(c, 0, sizeof(t_pdp_class)); + c->create = create; + c->type = type; // set type + pdp_list_add(class_list, a_pointer, (t_pdp_word)((void *)c)); + return c; +} + +/* the packet factory */ +int pdp_factory_newpacket(t_pdp_symbol *type) +{ + int p; + t_pdp_class *c; + t_pdp_atom *a = class_list->first; + + /* try to reuse first + THINK: should this be the responsability of the type specific constructors, + or should a packet allways be reusable (solution: depends on what the cleanup method returns??) + */ + p = pdp_packet_reuse(type); + if (-1 != p) return p; + + + /* call class constructor */ + while(a){ + c = (t_pdp_class *)(a->w.w_pointer); + if (c->type && pdp_type_description_match(type, c->type)){ + //pdp_post("method %x, type %s", c->create, type->s_name); + return (c->create) ? (*c->create)(type) : -1; + } + a = a->next; + } + return -1; +} + +static void +_pdp_pool_expand_nolock(void){ + int i; + + /* double the size */ + int new_pool_size = pdp_pool_size << 1; + t_pdp **new_pool = (t_pdp **)pdp_alloc(new_pool_size * sizeof(t_pdp *)); + bzero(new_pool, new_pool_size * sizeof(t_pdp *)); + memcpy(new_pool, pdp_pool, pdp_pool_size * sizeof(t_pdp *)); + pdp_dealloc(pdp_pool); + pdp_pool = new_pool; + pdp_pool_size = new_pool_size; +} + + + + +/* private _pdp_packet methods */ + +/* packets can only be created and destroyed using these 2 methods */ +/* it updates the mem usage and total packet count */ + +static void +_pdp_packet_dealloc_nolock(t_pdp *p) +{ + /* free memory */ + pdp_dealloc (p); +} + +static t_pdp* +_pdp_packet_alloc_nolock(unsigned int datatype, unsigned int datasize) +{ + unsigned int totalsize = datasize + PDP_HEADER_SIZE; + t_pdp *p = (t_pdp *)pdp_alloc(totalsize); + if (p){ + memset(p, 0, PDP_HEADER_SIZE); //initialize header to 0 + p->type = datatype; + p->size = totalsize; + p->users = 1; + } + return p; +} + + +/* create a new packet and expand pool if necessary */ +static int +_pdp_packet_create_nolock(unsigned int datatype, unsigned int datasize) +{ + int p = 0; + while(1){ + for (; p < pdp_pool_size; p++){ + if (!pdp_pool[p]){ + /* found slot to store packet*/ + t_pdp *header = _pdp_packet_alloc_nolock(datatype, datasize); + if (!header) return -1; // error allocating packet + pdp_pool[p] = header; + return p; + } + } + /* no slot found, expand pool */ + _pdp_pool_expand_nolock(); + } +} + + +void +pdp_packet_destroy(void) +{ + int i = 0; + /* dealloc all the data in object stack */ + pdp_post("DEBUG: pdp_packet_destroy: clearing object pool."); + while ((i < pdp_pool_size) && (pdp_pool[i])) _pdp_packet_dealloc_nolock(pdp_pool[i++]); +} + + + + + + + + +/* public pool operations: have to be thread safe so each entry point + locks the mutex */ + + +/* create a new packet. + this should only be used by type specific factory methods, and only if the + reuse method fails, since it will always create a new packet */ +int +pdp_packet_create(unsigned int datatype, unsigned int datasize /*without header*/) +{ + int packet; + LOCK; + packet = _pdp_packet_create_nolock(datatype, datasize); + UNLOCK; + return packet; +} + + +/* return a new packet. + it tries to reuse a packet based on + 1. matching data size + 2. abscence of destructor (which SHOULD mean there are no enclosed references) + + it obviously can't use the reuse fifo tagged to a symbolic type description + + ALWAYS USE pdp_packet_reuse BEFORE calling pdp_packet_new if possible + use both ONLY IN CONSTRUCTORS !!! + + use pdp_packet_factory to create packets as a "user" + + this is a summary of all internal packet creation mechanisms: + + -> pdp_packet_reuse, which uses symbolic type descriptions, and should work for all packet types + it returns an initialized container (meta = correct, data = garbage) + + -> pdp_packet_new, which only works for non-pure packets, and reuses packets based on data type + it returns a pure packet (meta + data = garbage) + + -> pdp_packet_create, like pdp_packet_new, only it always creates a new packet + + + +*/ + +int +pdp_packet_new(unsigned int datatype, unsigned int datasize) +{ + t_pdp *header; + int packet; + LOCK; + for (packet = 0; packet < pdp_pool_size; packet++){ + header = pdp_pool[packet]; + /* check data size */ + if (header + && header->users == 0 // must be unused + && header->size == datasize + PDP_HEADER_SIZE // must be same size + && !(header->theclass && header->theclass->cleanup)){ // must be pure packet (no destructor) + + /* ok, got one. initialize */ + memset(header, 0, PDP_HEADER_SIZE); + header->users = 1; + header->type = datatype; + header->size = datasize + PDP_HEADER_SIZE; + + UNLOCK; //EXIT1 + return packet; + } + } + + /* no usable non-pure packet found, create a new one */ + + UNLOCK; //EXIT2 + return pdp_packet_create(datatype, datasize); + + + +} + + +/* internal method to add a packet to a packet type + description symbol's unused packet fifo */ +void +_pdp_packet_save_nolock(int packet) +{ + t_pdp *header = pdp_packet_header(packet); + t_pdp_symbol *s; + PDP_ASSERT(header); + PDP_ASSERT(header->users == 0); + PDP_ASSERT(header->desc); + s = header->desc; + if (!s->s_reusefifo) s->s_reusefifo = pdp_list_new(0); + pdp_list_add(s->s_reusefifo, a_packet, (t_pdp_word)packet); +} + +/* this will revive a packet matching a certain type description + no wildcards are allowed */ +int +pdp_packet_reuse(t_pdp_symbol *type_description) +{ + int packet = -1; + t_pdp *header = 0; + t_pdp_list *l = 0; + LOCK; + if (!type_description || !(l = type_description->s_reusefifo)) goto exit; + while(l->elements){ + packet = pdp_list_pop(l).w_packet; + header = pdp_packet_header(packet); + + /* check if reuse fifo is consistent (packet unused + correct type) + packet could be deleted and replaced with another one, or + revived without the index updated (it's a "hint cache") */ + + if (header->users == 0){ + /* check if type matches */ + if (pdp_type_description_match(header->desc, type_description)){ + header->users++; // revive + goto exit; + } + /* if not, add the packet to the correct reuse fifo */ + else{ + _pdp_packet_save_nolock(packet); + } + } + + /* remove dangling refs */ + header = 0; + packet = -1; + } + + exit: + UNLOCK; + if (header && header->theclass && header->theclass->wakeup){ + header->theclass->wakeup(header); // revive if necessary + } + return packet; +} + +/* find all unused packets in pool, marked as used (to protect from other reapers) + and return them as a list. non-pure packets are not revived */ + + + + + +/* this returns a copy of a packet for read only access. + (increases refcount of the packet -> packet will become readonly if it was + writable, i.e. had rc=1 */ + +int +pdp_packet_copy_ro(int handle) +{ + t_pdp* header; + + if (header = pdp_packet_header(handle)){ + PDP_ASSERT(header->users); // consistency check + LOCK; + header->users++; // increment reference count + UNLOCK; + } + else handle = -1; + return handle; +} + +/* clone a packet: create a new packet with the same + type as the source packet */ + +int +pdp_packet_clone_rw(int handle) +{ + t_pdp* header; + int new_handle = -1; + + + if (header = pdp_packet_header(handle)){ + /* consistency checks */ + PDP_ASSERT(header->users); + PDP_ASSERT(header->desc); + + /* first try to reuse old packet */ + new_handle = pdp_packet_reuse(header->desc); + + /* if this failed, create a new one using the central packet factory method */ + if (-1 == new_handle) new_handle = pdp_factory_newpacket(header->desc); + + /* if the factory method failed cline it manually */ + if (-1 == new_handle) { + t_pdp *new_header; + //pdp_post("WARNING: pdp_clone_rw: working around non-implemented factory method."); + new_handle = pdp_packet_new(header->type, header->size - PDP_HEADER_SIZE); + new_header = pdp_packet_header(new_handle); + if (new_header){ + memcpy(new_header, header, PDP_HEADER_SIZE); + } + } + } + + return new_handle; +} + +/* return a copy of a packet (clone + copy data) */ +int +pdp_packet_copy_rw(int handle) +{ + t_pdp *header, *new_header; + int new_handle = -1; + + if (!(header = pdp_packet_header(handle))) return -1; + + /* check if we are allowed to copy */ + if (header->flags & PDP_FLAG_DONOTCOPY) return -1; + + /* get target packet */ + new_handle = pdp_packet_clone_rw(handle); + if (-1 == new_handle) return -1; + new_header = pdp_packet_header(new_handle); + + /* if there is a copy method, use that one */ + if (header->theclass && header->theclass->copy){ + header->theclass->copy(header, new_header); + } + + /* otherwize copy the data verbatim */ + else { + memcpy(pdp_packet_data(new_handle), + pdp_packet_data(handle), + pdp_packet_data_size(handle)); + } + + return new_handle; + +} + + +/* decrement refcount */ +void pdp_packet_mark_unused(int handle) +{ + t_pdp *header; + if (!(header = pdp_packet_header(handle))) return; + + PDP_ASSERT(header->users); // consistency check + + LOCK; + + /* just decrement refcount */ + if (header->users > 1){ + header->users--; + } + + /* put packet to sleep if refcount 1->0 */ + else { + if (header->theclass && header->theclass->sleep){ + /* call sleep method (if any) outside of lock + while the packet is still alive, so it won't be + acclaimed by another thread */ + UNLOCK; + header->theclass->sleep(header); + LOCK; + } + /* clear refcount & save in fifo for later use */ + header->users = 0; + if (header->desc) // sleep could have destructed packet.. + _pdp_packet_save_nolock(handle); + } + + UNLOCK; +} + + + +/* delete a packet. rc needs to be == 1 */ +void pdp_packet_delete(int handle) +{ + t_pdp *header; + header = pdp_packet_header(handle); + PDP_ASSERT(header); + PDP_ASSERT(header->users == 1); // consistency check + + LOCK; + + if (header->theclass && header->theclass->cleanup){ + /* call cleanup method (if any) outside of lock + while the packet is still alive, so it won't be + acclaimed by another thread */ + UNLOCK; + header->theclass->cleanup(header); + LOCK; + } + + /* delete the packet */ + pdp_pool[handle] = 0; + _pdp_packet_dealloc_nolock(header); + + + UNLOCK; +} + + + + + + + +/* public data access methods */ + +t_pdp* +pdp_packet_header(int handle) +{ + if ((handle >= 0) && (handle < pdp_pool_size)) return pdp_pool[handle]; + else return 0; +} + +void* +pdp_packet_subheader(int handle) +{ + t_pdp* header = pdp_packet_header(handle); + if (!header) return 0; + return (void *)(&header->info.raw); +} + +void* +pdp_packet_data(int handle) +{ + t_pdp *h; + if ((handle >= 0) && (handle < pdp_pool_size)) + { + h = pdp_pool[handle]; + if (!h) return 0; + return (char *)(h) + PDP_HEADER_SIZE; + } + else return 0; +} + +int +pdp_packet_data_size(int handle) +{ + t_pdp *h; + if ((handle >= 0) && (handle < pdp_pool_size)) + { + h = pdp_pool[handle]; + if (!h) return 0; + return h->size - PDP_HEADER_SIZE; + } + else return 0; +} + + + + +int pdp_packet_writable(int packet) /* returns true if packet is writable */ +{ + t_pdp *h = pdp_packet_header(packet); + if (!h) return 0; + return (h->users == 1); +} + +void pdp_packet_replace_with_writable(int *packet) /* replaces a packet with a writable copy */ +{ + int new_p; + if (!pdp_packet_writable(*packet)){ + new_p = pdp_packet_copy_rw(*packet); + pdp_packet_mark_unused(*packet); + *packet = new_p; + } + +} + +/* pool stuff */ + +int +pdp_pool_collect_garbage(void) +{ + pdp_post("ERROR: garbage collector not implemented"); + return 0; +} + +void +pdp_pool_set_max_mem_usage(int max) +{ + pdp_post("ERROR: mem limit not implemented"); +} + + + + + + +#ifdef __cplusplus +} +#endif diff --git a/system/kernel/pdp_packet2.c b/system/kernel/pdp_packet2.c new file mode 100644 index 0000000..3717a77 --- /dev/null +++ b/system/kernel/pdp_packet2.c @@ -0,0 +1,623 @@ +/* + * Pure Data Packet system implementation: Packet Manager + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + + + +#include <stdio.h> +#include <pthread.h> +#include <unistd.h> +#include <string.h> +#include "pdp_post.h" +#include "pdp_packet.h" +#include "pdp_mem.h" +#include "pdp_list.h" +#include "pdp_type.h" +#include "pdp_debug.h" + + +/* packet implementation. contains class and packet (instance) handling + + some notes on packet operations. + copy ro/rw and unregister are relatively straightforward + packet creation can be done in 2 ways in this interface: + create + reuse + however, these methods should only be called by specific factory + methods, so the user should only create packets using pdp_factory_newpacket + + reuse or create is thus the responsability of the factory methods for + each packet type (class) implementation + + +*/ + + +/* NOTE: + the packet pool methods are called within the pool locks. this probably + needs to change, because it will cause deadlocks for container packets (fobs) */ + + +/* new implementation: probably just a minor adjustment: add the reuse fifo attached + to type desc symbol name + need to check and possibly eliminate hacks for non-pure packets + + pdp_packet_new: + LOCK + 1. check reuse fifo + 2. empty -> create packet+return (search array) + 3. element -> check if type is correct, yes->pop+return, no->goto 1. + UNLOCK + 4. wakeup + + pdp_packet_mark_unused + + 1. check refcount. if > 1 dec + exit + 2. if 1 put packet to sleep + 3. dec refcount + 4. add to reuse fifo (no fifo -> create) + + pdp_packet_delete: analogous to mark_unused + pdp_packet_copy_ro/rw: analogous to new + +*/ + + +/* the pool */ +#define PDP_INITIAL_POOL_SIZE 64 +static int pdp_pool_size; +static t_pdp** pdp_pool; + +/* mutex: protects the pool and reuse lists attached to symbols */ +static pthread_mutex_t pdp_pool_mutex; +#define LOCK pthread_mutex_lock (&pdp_pool_mutex) +#define UNLOCK pthread_mutex_unlock (&pdp_pool_mutex) + +/* the list of classes */ +static t_pdp_list *class_list; + +/* debug */ +void +pdp_packet_print_debug(int packet) +{ + t_pdp *h = pdp_packet_header(packet); + pdp_post("debug info for packet %d", packet); + if (!h){ + pdp_post("invalid packet"); + } + else{ + pdp_post ("\ttype: %d", h->type); + pdp_post ("\tdesc: %s", h->desc ? h->desc->s_name : "unknown"); + pdp_post ("\tsize: %d", h->size); + pdp_post ("\tflags: %x", h->flags); + pdp_post ("\tusers: %d", h->users); + pdp_post ("\tclass: %x", h->theclass); + } +} + + + +/* setup methods */ + +void +pdp_packet_setup(void) +{ + + pdp_pool_size = PDP_INITIAL_POOL_SIZE; + pdp_pool = (t_pdp **)pdp_alloc(PDP_INITIAL_POOL_SIZE * sizeof(t_pdp *)); + bzero(pdp_pool, pdp_pool_size * sizeof(t_pdp *)); + class_list = pdp_list_new(0); + pthread_mutex_init(&pdp_pool_mutex, NULL); +} + +/* class methods */ +t_pdp_class *pdp_class_new(t_pdp_symbol *type, t_pdp_factory_method create){ + t_pdp_class *c = (t_pdp_class *)pdp_alloc(sizeof(t_pdp_class)); + memset(c, 0, sizeof(t_pdp_class)); + c->create = create; + c->type = type; // set type + pdp_list_add(class_list, a_pointer, (t_pdp_word)((void *)c)); + return c; +} + +/* the packet factory */ +int pdp_factory_newpacket(t_pdp_symbol *type) +{ + int p; + t_pdp_class *c; + t_pdp_atom *a = class_list->first; + + /* try to reuse first + THINK: should this be the responsability of the type specific constructors, + or should a packet allways be reusable (solution: depends on what the cleanup method returns??) + */ + p = pdp_packet_reuse(type); + if (-1 != p) return p; + + + /* call class constructor */ + while(a){ + c = (t_pdp_class *)(a->w.w_pointer); + if (c->type && pdp_type_description_match(type, c->type)){ + //pdp_post("method %x, type %s", c->create, type->s_name); + return (c->create) ? (*c->create)(type) : -1; + } + a = a->next; + } + return -1; +} + +static void +_pdp_pool_expand_nolock(void){ + int i; + + /* double the size */ + int new_pool_size = pdp_pool_size << 1; + t_pdp **new_pool = (t_pdp **)pdp_alloc(new_pool_size * sizeof(t_pdp *)); + bzero(new_pool, new_pool_size * sizeof(t_pdp *)); + memcpy(new_pool, pdp_pool, pdp_pool_size * sizeof(t_pdp *)); + pdp_dealloc(pdp_pool); + pdp_pool = new_pool; + pdp_pool_size = new_pool_size; +} + + + + +/* private _pdp_packet methods */ + +/* packets can only be created and destroyed using these 2 methods */ +/* it updates the mem usage and total packet count */ + +static void +_pdp_packet_dealloc_nolock(t_pdp *p) +{ + /* free memory */ + pdp_dealloc (p); +} + +static t_pdp* +_pdp_packet_alloc_nolock(unsigned int datatype, unsigned int datasize) +{ + unsigned int totalsize = datasize + PDP_HEADER_SIZE; + t_pdp *p = (t_pdp *)pdp_alloc(totalsize); + if (p){ + memset(p, 0, PDP_HEADER_SIZE); //initialize header to 0 + p->type = datatype; + p->size = totalsize; + p->users = 1; + } + return p; +} + + +/* create a new packet and expand pool if necessary */ +static int +_pdp_packet_create_nolock(unsigned int datatype, unsigned int datasize) +{ + int p = 0; + while(1){ + for (; p < pdp_pool_size; p++){ + if (!pdp_pool[p]){ + /* found slot to store packet*/ + t_pdp *header = _pdp_packet_alloc_nolock(datatype, datasize); + if (!header) return -1; // error allocating packet + pdp_pool[p] = header; + return p; + } + } + /* no slot found, expand pool */ + _pdp_pool_expand_nolock(); + } +} + + +void +pdp_packet_destroy(void) +{ + int i = 0; + /* dealloc all the data in object stack */ + pdp_post("DEBUG: pdp_packet_destroy: clearing object pool."); + while ((i < pdp_pool_size) && (pdp_pool[i])) _pdp_packet_dealloc_nolock(pdp_pool[i++]); +} + + + + + + + + +/* public pool operations: have to be thread safe so each entry point + locks the mutex */ + + +/* create a new packet. + this should only be used by type specific factory methods, and only if the + reuse method fails, since it will always create a new packet */ +int +pdp_packet_create(unsigned int datatype, unsigned int datasize /*without header*/) +{ + int packet; + LOCK; + packet = _pdp_packet_create_nolock(datatype, datasize); + UNLOCK; + return packet; +} + + +/* return a new packet. + it tries to reuse a packet based on + 1. matching data size + 2. abscence of destructor (which SHOULD mean there are no enclosed references) + + it obviously can't use the reuse fifo tagged to a symbolic type description + + ALWAYS USE pdp_packet_reuse BEFORE calling pdp_packet_new if possible + use both ONLY IN CONSTRUCTORS !!! + + use pdp_packet_factory to create packets as a "user" + + this is a summary of all internal packet creation mechanisms: + + -> pdp_packet_reuse, which uses symbolic type descriptions, and should work for all packet types + it returns an initialized container (meta = correct, data = garbage) + + -> pdp_packet_new, which only works for non-pure packets, and reuses packets based on data type + it returns a pure packet (meta + data = garbage) + + -> pdp_packet_create, like pdp_packet_new, only it always creates a new packet + + + +*/ + +int +pdp_packet_new(unsigned int datatype, unsigned int datasize) +{ + t_pdp *header; + int packet; + LOCK; + for (packet = 0; packet < pdp_pool_size; packet++){ + header = pdp_pool[packet]; + /* check data size */ + if (header + && header->users == 0 + && header->size == datasize + PDP_HEADER_SIZE + && !(header->theclass && header->theclass->cleanup)){ + + /* ok, got one. initialize */ + memset(header, 0, PDP_HEADER_SIZE); + header->users = 1; + header->type = datatype; + header->size = datasize + PDP_HEADER_SIZE; + + UNLOCK; //EXIT1 + return packet; + } + } + + /* no usable non-pure packet found, create a new one */ + + UNLOCK; //EXIT2 + return pdp_packet_create(datatype, datasize); + + + +} + + +/* internal method to add a packet to a packet type + description symbol's unused packet fifo */ +void +_pdp_packet_save_nolock(int packet) +{ + t_pdp *header = pdp_packet_header(packet); + t_pdp_symbol *s; + PDP_ASSERT(header); + PDP_ASSERT(header->users == 0); + PDP_ASSERT(header->desc); + s = header->desc; + if (!s->s_reusefifo) s->s_reusefifo = pdp_list_new(0); + pdp_list_add(s->s_reusefifo, a_packet, (t_pdp_word)packet); +} + +/* this will revive a packet matching a certain type description + no wildcards are allowed */ +int +pdp_packet_reuse(t_pdp_symbol *type_description) +{ + int packet = -1; + t_pdp *header = 0; + t_pdp_list *l = 0; + LOCK; + if (!type_description || !(l = type_description->s_reusefifo)) goto exit; + while(l->elements){ + packet = pdp_list_pop(l).w_packet; + header = pdp_packet_header(packet); + + /* check if reuse fifo is consistent (packet unused + correct type) + packet could be deleted and replaced with another one, or + revived without the index updated (it's a "hint cache") */ + + if (header->users == 0){ + /* check if type matches */ + if (pdp_type_description_match(header->desc, type_description)){ + header->users++; // revive + goto exit; + } + /* if not, add the packet to the correct reuse fifo */ + else{ + _pdp_packet_save_nolock(packet); + } + } + + /* remove dangling refs */ + header = 0; + packet = -1; + } + + exit: + UNLOCK; + if (header && header->theclass && header->theclass->wakeup){ + header->theclass->wakeup(header); // revive if necessary + } + return packet; +} + +/* find all unused packets in pool, marked as used (to protect from other reapers) + and return them as a list. non-pure packets are not revived */ + + + + + +/* this returns a copy of a packet for read only access. + (increases refcount of the packet -> packet will become readonly if it was + writable, i.e. had rc=1 */ + +int +pdp_packet_copy_ro(int handle) +{ + t_pdp* header; + + if (header = pdp_packet_header(handle)){ + PDP_ASSERT(header->users); // consistency check + LOCK; + header->users++; // increment reference count + UNLOCK; + } + else handle = -1; + return handle; +} + +/* clone a packet: create a new packet with the same + type as the source packet */ + +int +pdp_packet_clone_rw(int handle) +{ + t_pdp* header; + int new_handle = -1; + + + if (header = pdp_packet_header(handle)){ + /* consistency checks */ + PDP_ASSERT(header->users); + PDP_ASSERT(header->desc); + + /* first try to reuse old packet */ + new_handle = pdp_packet_reuse(header->desc); + + /* if this failed, create a new one using the central packet factory method */ + if (-1 == new_handle) new_handle = pdp_factory_newpacket(header->desc); + } + + return new_handle; +} + +/* return a copy of a packet (clone + copy data) */ +int +pdp_packet_copy_rw(int handle) +{ + t_pdp *header, *new_header; + int new_handle = -1; + + if (!(header = pdp_packet_header(handle))) return -1; + + /* check if we are allowed to copy */ + if (header->flags & PDP_FLAG_DONOTCOPY) return -1; + + /* get target packet */ + new_handle = pdp_packet_clone_rw(handle); + if (-1 == new_handle) return -1; + new_header = pdp_packet_header(new_handle); + + /* if there is a copy method, use that one */ + if (header->theclass && header->theclass->copy){ + header->theclass->copy(header, new_header); + } + + /* otherwize copy the data verbatim */ + else { + memcpy(pdp_packet_data(new_handle), + pdp_packet_data(handle), + pdp_packet_data_size(handle)); + } + + return new_handle; + +} + + +/* decrement refcount */ +void pdp_packet_mark_unused(int handle) +{ + t_pdp *header; + if (!(header = pdp_packet_header(handle))) return; + + PDP_ASSERT(header->users); // consistency check + + LOCK; + + /* just decrement refcount */ + if (header->users > 1){ + header->users--; + } + + /* put packet to sleep if refcount 1->0 */ + else { + if (header->theclass && header->theclass->sleep){ + /* call sleep method (if any) outside of lock + while the packet is still alive, so it won't be + acclaimed by another thread */ + UNLOCK; + header->theclass->sleep(header); + LOCK; + } + /* clear refcount & save in fifo for later use */ + header->users = 0; + if (header->desc) // sleep could have destructed packet.. + _pdp_packet_save_nolock(handle); + } + + UNLOCK; +} + + + +/* delete a packet. rc needs to be == 1 */ +void pdp_packet_delete(int handle) +{ + t_pdp *header; + header = pdp_packet_header(handle); + PDP_ASSERT(header); + PDP_ASSERT(header->users == 1); // consistency check + + LOCK; + + if (header->theclass && header->theclass->cleanup){ + /* call cleanup method (if any) outside of lock + while the packet is still alive, so it won't be + acclaimed by another thread */ + UNLOCK; + header->theclass->cleanup(header); + LOCK; + } + + /* delete the packet */ + pdp_pool[handle] = 0; + _pdp_packet_dealloc_nolock(header); + + + UNLOCK; +} + + + + + + + +/* public data access methods */ + +t_pdp* +pdp_packet_header(int handle) +{ + if ((handle >= 0) && (handle < pdp_pool_size)) return pdp_pool[handle]; + else return 0; +} + +void* +pdp_packet_subheader(int handle) +{ + t_pdp* header = pdp_packet_header(handle); + if (!header) return 0; + return (void *)(&header->info.raw); +} + +void* +pdp_packet_data(int handle) +{ + t_pdp *h; + if ((handle >= 0) && (handle < pdp_pool_size)) + { + h = pdp_pool[handle]; + if (!h) return 0; + return (char *)(h) + PDP_HEADER_SIZE; + } + else return 0; +} + +int +pdp_packet_data_size(int handle) +{ + t_pdp *h; + if ((handle >= 0) && (handle < pdp_pool_size)) + { + h = pdp_pool[handle]; + if (!h) return 0; + return h->size - PDP_HEADER_SIZE; + } + else return 0; +} + + + + +int pdp_packet_writable(int packet) /* returns true if packet is writable */ +{ + t_pdp *h = pdp_packet_header(packet); + if (!h) return 0; + return (h->users == 1); +} + +void pdp_packet_replace_with_writable(int *packet) /* replaces a packet with a writable copy */ +{ + int new_p; + if (!pdp_packet_writable(*packet)){ + new_p = pdp_packet_copy_rw(*packet); + pdp_packet_mark_unused(*packet); + *packet = new_p; + } + +} + +/* pool stuff */ + +int +pdp_pool_collect_garbage(void) +{ + pdp_post("ERROR: garbage collector not implemented"); + return 0; +} + +void +pdp_pool_set_max_mem_usage(int max) +{ + pdp_post("ERROR: mem limit not implemented"); +} + + + + + + +#ifdef __cplusplus +} +#endif diff --git a/system/kernel/pdp_post.c b/system/kernel/pdp_post.c new file mode 100644 index 0000000..fb761d0 --- /dev/null +++ b/system/kernel/pdp_post.c @@ -0,0 +1,48 @@ + +/* + * Pure Data Packet system file. pdp logging. + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + +#include <stdlib.h> +#include <stdio.h> +#include <stdarg.h> +#include <string.h> +#include <errno.h> +#include "pdp_post.h" + +/* list printing should be moved here too */ + +/* write a message to log (console) */ +void pdp_post_n(char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); +} +void pdp_post(char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); + putc('\n', stderr); +} + + diff --git a/system/kernel/pdp_symbol.c b/system/kernel/pdp_symbol.c new file mode 100644 index 0000000..32e9e33 --- /dev/null +++ b/system/kernel/pdp_symbol.c @@ -0,0 +1,196 @@ +/* + * Pure Data Packet system implementation. : code implementing pdp's namespace (symbols) + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + +#include <string.h> +#include <pthread.h> +#include "pdp_symbol.h" +#include "pdp_list.h" +#include "pdp_debug.h" + +// some extra prototypes +void *pdp_alloc(int size); +void pdp_dealloc(void *data); + +// the symbol hash mutex +static pthread_mutex_t pdp_hash_mutex; + +#define HASHSIZE 1024 +static t_pdp_symbol *pdp_symhash[HASHSIZE]; + + +#define LOCK pthread_mutex_lock(&pdp_hash_mutex) +#define UNLOCK pthread_mutex_unlock(&pdp_hash_mutex) + + +static void _pdp_symbol_init(t_pdp_symbol *s) +{ + memset(s, 0, sizeof(*s)); + s->s_forth.t = a_undef; +} + + +/* shamelessly copied from pd src and made thread safe */ +t_pdp_symbol *_pdp_dogensym(char *s, t_pdp_symbol *oldsym) +{ + t_pdp_symbol **sym1, *sym2; + unsigned int hash1 = 0, hash2 = 0; + int length = 0; + char *s2 = s; + while (*s2) + { + hash1 += *s2; + hash2 += hash1; + length++; + s2++; + } + sym1 = pdp_symhash + (hash2 & (HASHSIZE-1)); + + /* lock hash */ + LOCK; + + while (sym2 = *sym1) + { + if (!strcmp(sym2->s_name, s)) goto gotit; + sym1 = &sym2->s_next; + } + if (oldsym){ + sym2 = oldsym; + } + else + { + sym2 = (t_pdp_symbol *)pdp_alloc(sizeof(*sym2)); + _pdp_symbol_init(sym2); + sym2->s_name = pdp_alloc(length+1); + sym2->s_next = 0; + strcpy(sym2->s_name, s); + } + *sym1 = sym2; + + gotit: + + /* unlock hash */ + UNLOCK; + return (sym2); +} + +t_pdp_symbol *pdp_gensym(char *s) +{ + return(_pdp_dogensym(s, 0)); +} + + +/* connect a parsed typelist to a symbol type name + 1 = succes, 0 = error (symbol already connected) */ +int pdp_symbol_set_typelist(t_pdp_symbol *s, t_pdp_list *typelist) +{ + int status = 0; + LOCK; + if (!s->s_type){ + s->s_type = typelist; + status = 1; + } + UNLOCK; + return status; +} + + +void pdp_symbol_apply_all(t_pdp_symbol_iterator it) +{ + int i; + for (i=0; i<HASHSIZE; i++){ + t_pdp_symbol *s; + for (s = pdp_symhash[i]; s; s=s->s_next){ + it(s); + } + + } +} + +t_pdp_symbol _pdp_sym_wildcard; +t_pdp_symbol _pdp_sym_float; +t_pdp_symbol _pdp_sym_int; +t_pdp_symbol _pdp_sym_symbol; +t_pdp_symbol _pdp_sym_packet; +t_pdp_symbol _pdp_sym_pointer; +t_pdp_symbol _pdp_sym_invalid; +t_pdp_symbol _pdp_sym_list; +t_pdp_symbol _pdp_sym_question_mark; +t_pdp_symbol _pdp_sym_atom; +t_pdp_symbol _pdp_sym_null; +t_pdp_symbol _pdp_sym_quote_start; +t_pdp_symbol _pdp_sym_quote_end; +t_pdp_symbol _pdp_sym_return; +t_pdp_symbol _pdp_sym_nreturn; +t_pdp_symbol _pdp_sym_defstart; +t_pdp_symbol _pdp_sym_defend; +t_pdp_symbol _pdp_sym_if; +t_pdp_symbol _pdp_sym_then; +t_pdp_symbol _pdp_sym_local; +t_pdp_symbol _pdp_sym_forth; +t_pdp_symbol _pdp_sym_call; +t_pdp_symbol _pdp_sym_push; +t_pdp_symbol _pdp_sym_pop; + +static void _sym(char *name, t_pdp_symbol *s) +{ + t_pdp_symbol *realsym; + _pdp_symbol_init(s); + s->s_name = name; + realsym = _pdp_dogensym(name, s); + PDP_ASSERT(realsym == s); // if this fails, the symbol was already defined +} + +void pdp_symbol_setup(void) +{ + // create mutexes + pthread_mutex_init(&pdp_hash_mutex, NULL); + + // init symbol hash + memset(pdp_symhash, 0, HASHSIZE * sizeof(t_pdp_symbol *)); + + // setup predefined symbols (those that have direct pointer access for speedup) + _sym("*", &_pdp_sym_wildcard); + _sym("float", &_pdp_sym_float); + _sym("int", &_pdp_sym_int); + _sym("symbol", &_pdp_sym_symbol); + _sym("packet", &_pdp_sym_packet); + _sym("pointer", &_pdp_sym_pointer); + _sym("invalid", &_pdp_sym_invalid); + _sym("list", &_pdp_sym_list); + _sym("?", &_pdp_sym_question_mark); + _sym("atom", &_pdp_sym_atom); + _sym("null", &_pdp_sym_null); + _sym("[", &_pdp_sym_quote_start); + _sym("]", &_pdp_sym_quote_end); + _sym("ret", &_pdp_sym_return); + _sym("nret", &_pdp_sym_nreturn); + _sym(":", &_pdp_sym_defstart); + _sym(";", &_pdp_sym_defend); + _sym("if", &_pdp_sym_if); + _sym("then", &_pdp_sym_then); + _sym("local", &_pdp_sym_local); + _sym("forth", &_pdp_sym_forth); + _sym("call", &_pdp_sym_call); + _sym("push", &_pdp_sym_push); + _sym("pop", &_pdp_sym_pop); + +} + + diff --git a/system/kernel/pdp_type.c b/system/kernel/pdp_type.c new file mode 100644 index 0000000..0216d07 --- /dev/null +++ b/system/kernel/pdp_type.c @@ -0,0 +1,473 @@ +/* + * Pure Data Packet system implementation. : code for handling different packet types + * Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + */ + + +/* this file contains type handling routines */ + +#include <stdarg.h> +#include <string.h> +#include <pthread.h> +#include "pdp_list.h" +#include "pdp_symbol.h" +#include "pdp_packet.h" +#include "pdp_post.h" +#include "pdp_type.h" +#include "pdp_mem.h" +#include "pdp_debug.h" + + +// debug +#define D if (0) + + +static t_pdp_list *conversion_list; + +#define INIT_MAX_CACHE_SIZE 32 + +static t_pdp_list *cached_conversion_list; +static int max_cache_size; + +/* mutex */ +static pthread_mutex_t pdp_conversion_mutex; +static pthread_mutex_t pdp_cache_mutex; + + + +/* convert a type to a list */ +t_pdp_list *pdp_type_to_list(t_pdp_symbol *type) +{ +#define TMPSIZE 1024 + + char *c = type->s_name; + char *lastname = c; + int n = 0; + char tmp[strlen(type->s_name)+1]; + t_pdp_list *l = pdp_list_new(0); + + while(*c){ + if (*c == '/'){ + strncpy(tmp, lastname, n); + tmp[n] = 0; + pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(tmp)); + c++; + lastname = c; + n = 0; + } + else{ + c++; + n++; + PDP_ASSERT(n < TMPSIZE); + } + } + pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(lastname)); + + return l; +} + + +/* get the description symbol. */ +t_pdp_symbol *pdp_packet_get_description(int packet) +{ + t_pdp *header = pdp_packet_header(packet); + + if (!header) return pdp_gensym("invalid"); + else if (!header->desc){ + + /* since every packet is obliged to have a description, this is an error */ + pdp_post("ERROR: pdp_packet_get_description: packet %d has no description.", packet); + pdp_packet_print_debug(packet); + return pdp_gensym("unknown"); + } + else return header->desc; +} + + + +/* this runs a conversion program */ +int _pdp_type_run_conversion_program(t_pdp_conversion_program *program, + int packet, t_pdp_symbol *dest_template) +{ + /* run a conversion program: + treat the source packet as readonly, and cleanup intermediates, such + that the net result is the production of a new packet, with the + source packet intact. */ + + int p, tmp; + t_pdp_atom *a; + t_pdp_conversion_method m; + + // run the first line of the program + a = program->first; + m = a->w.w_pointer; + D pdp_post("DEBUG: _pdp_type_run_conversion_program: method = %x", m); + p = m(packet, dest_template); + D pdp_post("DEBUG: _pdp_type_run_conversion_program:"); + D pdp_post(" packet returned = %d, type = %s", + p, pdp_packet_get_description(p)->s_name); + + // run the remaining lines + cleanup intermediates + for (a=a->next; a; a=a->next){ + m = a->w.w_pointer; + D pdp_post("DEBUG: _pdp_type_run_conversion_program: next method ptr = %x", m); + tmp = m(p, dest_template); + pdp_packet_mark_unused(p); + p = tmp; + } + return p; +} + + +/* find a conversion program */ +t_pdp_conversion_program * +_pdp_type_find_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern) +{ + t_pdp_conversion *c; + t_pdp_atom *a; + t_pdp_conversion_program *retval = 0; + + /* lock conversion list */ + pthread_mutex_lock(&pdp_conversion_mutex); + + for (a = conversion_list->first; a; a=a->next){ + c = a->w.w_pointer; + /* can be a wildcard match */ + if (pdp_type_description_match(src_pattern, c->src_pattern) && + pdp_type_description_match(dst_pattern, c->dst_pattern)) { + /* found a program */ + D pdp_post("DEBUG: _pdp_type_find_conversion_program: found: %s -> %s", + c->src_pattern->s_name, c->dst_pattern->s_name); + retval = c->program; + goto gotit; + } + } + + /* no conversion program was found */ + retval = 0; + gotit: + + /* lock conversion list */ + pthread_mutex_unlock(&pdp_conversion_mutex); + return retval; +} + +/* find a cached conversion program + if one is found it will be moved to the back of the queue (MRU) */ +t_pdp_conversion_program * +_pdp_type_find_cached_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern) +{ + t_pdp_conversion *c, *c_tmp; + t_pdp_atom *a; + t_pdp_conversion_program *retval = 0; + + /* lock cached list */ + pthread_mutex_lock(&pdp_cache_mutex); + + for (a = cached_conversion_list->first; a; a=a->next){ + c = a->w.w_pointer; + /* must be exact match */ + if ((src_pattern == c->src_pattern) && + (dst_pattern == c->dst_pattern)) { + + /* found a program */ + D pdp_post("DEBUG: _pdp_type_find_cached_conversion_program: found: %s -> %s", + c->src_pattern->s_name, c->dst_pattern->s_name); + retval = c->program; + + /* make MRU (move to back) */ + c_tmp = cached_conversion_list->last->w.w_pointer; + cached_conversion_list->last->w.w_pointer = c; + a->w.w_pointer = c_tmp; + goto gotit; + } + } + + retval = 0; + + gotit: + + + /* un lock cached list */ + pthread_mutex_unlock(&pdp_cache_mutex); + + /* no conversion program was found */ + return retval; +} + + +/* conversion program manipulations */ +void pdp_conversion_program_free(t_pdp_conversion_program *program) +{ + pdp_list_free(program); +} + +/* debug print */ +void _pdp_conversion_program_print(t_pdp_conversion_program *program) +{ + D pdp_post("_pdp_conversion_program_print %x", program); + pdp_list_print(program); +} + +t_pdp_conversion_program *pdp_conversion_program_new(t_pdp_conversion_method method, ...) +{ + t_pdp_conversion_program *p = pdp_list_new(0); + t_pdp_conversion_method m = method; + va_list ap; + + D pdp_post("DEBUG: pdp_conversion_program_new:BEGIN"); + + pdp_list_add_back_pointer(p, m); + va_start(ap, method); + while (m = va_arg(ap, t_pdp_conversion_method)) pdp_list_add_back_pointer(p, m); + va_end(ap); + + D pdp_post("DEBUG: pdp_conversion_program_new:END"); + + return p; +} + +t_pdp_conversion_program *pdp_conversion_program_copy(t_pdp_conversion_program *program) +{ + if (program) return pdp_list_copy(program); + else return 0; +} + +void pdp_conversion_program_add(t_pdp_conversion_program *program, + t_pdp_conversion_program *tail) +{ + return pdp_list_cat(program, tail); +} + +/* conversion registration */ +void pdp_type_register_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern, + t_pdp_conversion_program *program) +{ + t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c)); + c->src_pattern = src_pattern; + c->dst_pattern = dst_pattern; + c->program = program; + + /* lock conversion list */ + pthread_mutex_lock(&pdp_conversion_mutex); + + pdp_list_add_back_pointer(conversion_list, c); + + /* unlock conversion list */ + pthread_mutex_unlock(&pdp_conversion_mutex); + +} + +/* register a cached conversion */ +void pdp_type_register_cached_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern, t_pdp_conversion_program *program) +{ + + /* create the new conversion */ + t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c)); + c->src_pattern = src_pattern; + c->dst_pattern = dst_pattern; + c->program = program; + + /* lock cached conversion list */ + pthread_mutex_lock(&pdp_cache_mutex); + + /* check size, and remove LRU (top) if the cache is full */ + while (cached_conversion_list->elements >= max_cache_size){ + t_pdp_conversion *c_old = pdp_list_pop(cached_conversion_list).w_pointer; + if (c_old->program) pdp_conversion_program_free(c_old->program); + pdp_dealloc(c_old); + } + + /* add and make MRU (back) */ + pdp_list_add_back_pointer(cached_conversion_list, c); + + /* unlock cached conversion list */ + pthread_mutex_unlock(&pdp_cache_mutex); +} + +/* convert a given packet to a certain type (template) */ +int _pdp_packet_convert(int packet, t_pdp_symbol *dest_template) +{ + t_pdp_symbol *type = pdp_packet_get_description(packet); + t_pdp_symbol *tmp_type = 0; + int tmp_packet = -1; + + t_pdp_conversion_program *program = 0; + t_pdp_conversion_program *program_last = 0; + t_pdp_conversion_program *program_tail = 0; + + /* check if there is a program in the cached list, if so run it */ + if (program = _pdp_type_find_cached_conversion_program(type, dest_template)) + return _pdp_type_run_conversion_program(program, packet, dest_template); + + /* if it is not cached, iteratively convert + and save program on top of cache list if a conversion path (program) was found */ + + // run first conversion that matches + program = pdp_conversion_program_copy + (_pdp_type_find_conversion_program(type, dest_template)); + program_last = program; + if (!program){ + D pdp_post("DEBUG: pdp_type_convert: (1) can't convert %s to %s", + type->s_name, dest_template->s_name); + return -1; + } + tmp_packet = _pdp_type_run_conversion_program(program, packet, dest_template); + tmp_type = pdp_packet_get_description(tmp_packet); + + // run more conversions if necessary, deleting intermediate packets + while (!pdp_type_description_match(tmp_type, dest_template)){ + int new_packet; + program_tail = _pdp_type_find_conversion_program(tmp_type, dest_template); + if (!program_tail){ + D pdp_post("DEBUG: pdp_type_convert: (2) can't convert %s to %s", + tmp_type->s_name, dest_template->s_name); + pdp_packet_mark_unused(tmp_packet); + pdp_conversion_program_free(program); + return -1; + } + if (program_last == program_tail){ + pdp_post("ERROR: pdp_packet_convert: conversion loop detected"); + } + program_last = program_tail; + + pdp_conversion_program_add(program, program_tail); + new_packet = _pdp_type_run_conversion_program(program_tail, tmp_packet, dest_template); + pdp_packet_mark_unused(tmp_packet); + tmp_packet = new_packet; + tmp_type = pdp_packet_get_description(tmp_packet); + } + + // save the conversion program in the cache + pdp_type_register_cached_conversion(type, dest_template, program); + + // return resulting packet + return tmp_packet; + +} + +/* convert or copy ro */ +int pdp_packet_convert_ro(int packet, t_pdp_symbol *dest_template) +{ + t_pdp_symbol *type = pdp_packet_get_description(packet); + + /* if it is compatible, return a ro copy */ + if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_ro(packet); + + /* if not, convert to a new type */ + else return _pdp_packet_convert(packet, dest_template); +} + +/* convert or copy rw */ +int pdp_packet_convert_rw(int packet, t_pdp_symbol *dest_template) +{ + t_pdp_symbol *type = pdp_packet_get_description(packet); + + /* if it is compatible, just return a rw copy */ + if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_rw(packet); + + /* if not, convert to a new type */ + else return _pdp_packet_convert(packet, dest_template); +} + + +/* this is a hack. type cache data: (a type description parsed into + a pdp_list for fast comparison) should be setup when + a packet symbol is created, but since that can be everywhere, + we set it up on first use. type cache is permanent. */ + + +static void _setup_type_cache(t_pdp_symbol *s) +{ + t_pdp_list *l = pdp_type_to_list(s); + if (!pdp_symbol_set_typelist(s, l)) + pdp_list_free(l); // list was already present -> free cached list + +} + +/* check if a type description fits a template + this function is symmetric */ +int pdp_type_description_match(t_pdp_symbol *description, t_pdp_symbol *pattern) +{ + int match = 0; // no match until all tests are passed + + t_pdp_atom *ad, *ap; + t_pdp_symbol *wildcard = PDP_SYM_WILDCARD; + + PDP_ASSERT(pattern); + PDP_ASSERT(description); + + /* same type symbol -> match */ + if (description == pattern) {match = 1; goto done;} + + /* check the description list */ + if (!(description->s_type)) _setup_type_cache(description); + if (!(pattern->s_type)) _setup_type_cache(pattern); + + /* compare symbols of description list */ + for(ad=description->s_type->first, ap=pattern->s_type->first; + ad && ap; + ad=ad->next, ap=ap->next) + { + + if (ad->w.w_symbol == wildcard) continue; + if (ap->w.w_symbol == wildcard) continue; + if (ad->w.w_symbol != ap->w.w_symbol) {goto done;} /* difference and not a wildcard */ + } + + /* ok if sizes are equal */ + if (! (ad || ap)) {match = 1; goto done;} + + /* one of the two is shorter, so the shortest list needs + to end with a wildcard to have a match */ + + if (ap && description->s_type->last->w.w_symbol != wildcard) goto done; + if (ad && pattern->s_type->last->w.w_symbol != wildcard) goto done; + + /* all tests passed: type templates match */ + match = 1; + + done: + D pdp_post("DEBUG: testing match between %s and %s: %s", + description->s_name, pattern->s_name, match ? "match" : "no match"); + return match; + +} + + + + + +/* setup method */ +void pdp_type_setup(void) +{ + int i; + + // create mutexes + pthread_mutex_init(&pdp_conversion_mutex, NULL); + pthread_mutex_init(&pdp_cache_mutex, NULL); + + // create conversion lists + cached_conversion_list = pdp_list_new(0); + conversion_list = pdp_list_new(0); + max_cache_size = INIT_MAX_CACHE_SIZE; + + + + +} |