source: src/Concurrency/Waitfor.cc @ b81fd95

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since b81fd95 was b81fd95, checked in by Michael Brooks <mlbrooks@…>, 15 months ago

Fix bug where pointer and reference types allow unsound initialization and return. Fixes #189

There are two instances of the same basic change, which is using conversionCost instead of castCost for resolving...
A: an InitExpr?, always; affects variable initializations
B: a CastExpr?, for type-system-generated casts only; affects function returns

Changing the behaviour of the typechecker on initialization (do A) and cast (do B):
src/ResolvExpr/AlternativeFinder.cc
src/SynTree/Expression.h
testsinit1.*

Making type of string literal consistent with how C defines it (accommodate A):
src/Parser/ExpressionNode.cc

Making type system happy with incumbent use of void* (accommodate A):
libcfa/src/concurrency/kernel.cfa
libcfa/src/containers/list.hfa
tests/bugs/66.cfa
tests/avltree/avl1.cfa
tests/concurrent/signal/block.cfa
tests/searchsort.cfa

Making type system happy with incumbent plan-9 downcast (accommodate B):
libcfa/src/containers/list.hfa

Fixing previously incorrect constness of declarations (accommodate A):
tests/exceptions/defaults.cfa
libcfa/src/iostream.hfa

Fixing previously incorrect isGenerated classification of casts that desugaring introduces (accommodate B):
src/Concurrency/Keywords.cc
src/Concurrency/Waitfor.cc

Working around trac #207 (revealed by A):
tests/io2.cfa

Working around trac #208 (speculatively created by B):
libcfa/src/bits/locks.hfa
libcfa/src/concurrency/preemption.cfa

Misc:
tests/exceptions/conditional.cfa (accommodate A)

a _msg function for an exception was declared with wrong return type, so it was not compatible for assignment into the vtable instance

libcfa/src/stdlib.hfa

the compiler now prohibits a prior attempt to call a nonexistent realloc overload; calling alloc_align in its place

  • Property mode set to 100644
File size: 15.4 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Waitfor.cc --
8//
9// Author           : Thierry Delisle
10// Created On       : Mon Aug 28 11:06:52 2017
11// Last Modified By :
12// Last Modified On :
13// Update Count     : 12
14//
15
16#include "Concurrency/Keywords.h"
17
18#include <cassert>                 // for assert
19#include <string>                  // for string, operator==
20
21using namespace std::string_literals;
22
23#include "Common/PassVisitor.h"    // for PassVisitor
24#include "Common/SemanticError.h"  // for SemanticError
25#include "Common/UniqueName.h"     // for UniqueName
26#include "Common/utility.h"        // for deleteAll, map_range
27#include "CodeGen/OperatorTable.h" // for isConstructor
28#include "InitTweak/InitTweak.h"   // for getPointerBase
29#include "ResolvExpr/Resolver.h"   // for findVoidExpression
30#include "SynTree/LinkageSpec.h"   // for Cforall
31#include "SynTree/Constant.h"      // for Constant
32#include "SynTree/Declaration.h"   // for StructDecl, FunctionDecl, ObjectDecl
33#include "SynTree/Expression.h"    // for VariableExpr, ConstantExpr, Untype...
34#include "SynTree/Initializer.h"   // for SingleInit, ListInit, Initializer ...
35#include "SynTree/Label.h"         // for Label
36#include "SynTree/Statement.h"     // for CompoundStmt, DeclStmt, ExprStmt
37#include "SynTree/Type.h"          // for StructInstType, Type, PointerType
38#include "SynTree/Visitor.h"       // for Visitor, acceptAll
39
40class Attribute;
41/*
42void foo() {
43        while( true ) {
44                when( a < 1 ) waitfor( f : a ) { bar(); }
45                or timeout( swagl() );
46                or waitfor( g : a ) { baz(); }
47                or waitfor( ^?{} : a ) { break; }
48                or waitfor( ^?{} ) { break; }
49        }
50}
51
52void f(int i, float f, A & mutex b, struct foo *  );
53void f(int );
54
55
56                      |  |
57                      |  |
58                            |  |
59                      |  |
60                      |  |
61                    \ |  | /
62                     \    /
63                      \  /
64                       \/
65
66
67void foo() {
68        while( true ) {
69                {
70                        acceptable_t acceptables[3];
71                        if( a < 1 ) {
72                                acceptables[0].func = f;
73                                acceptables[0].mon = a;
74                        }
75                        acceptables[1].func = g;
76                        acceptables[1].mon = a;
77
78                        acceptables[2].func = f;
79                        acceptables[2].mon = a;
80                        acceptables[2].is_dtor = true;
81
82                        int ret = waitfor_internal( acceptables, swagl() );
83
84                        switch( ret ) {
85                                case 0:
86                                {
87                                        bar();
88                                }
89                                case 1:
90                                {
91                                        baz();
92                                }
93                                case 2:
94                                        signal(a);
95                                        {
96                                                break;
97                                        }
98                        }
99                }
100        }
101}*/
102
103namespace Concurrency {
104        //=============================================================================================
105        // Pass declarations
106        //=============================================================================================
107
108        class GenerateWaitForPass final : public WithIndexer {
109          public:
110
111                void premutate( FunctionDecl * decl );
112                void premutate( StructDecl   * decl );
113
114                Statement * postmutate( WaitForStmt * stmt );
115
116                static void generate( std::list< Declaration * > & translationUnit ) {
117                        PassVisitor< GenerateWaitForPass > impl;
118                        acceptAll( translationUnit, impl );
119                }
120
121                ObjectDecl * declare( unsigned long count, CompoundStmt * stmt );
122                ObjectDecl * declareFlag( CompoundStmt * stmt );
123                Statement  * makeSetter( ObjectDecl * flag );
124                ObjectDecl * declMon( WaitForStmt::Clause & clause, CompoundStmt * stmt );
125                void         init( ObjectDecl * acceptables, int index, WaitForStmt::Clause & clause, Statement * settter, CompoundStmt * stmt );
126                Expression * init_timeout( Expression *& time, Expression *& time_cond, bool has_else, Expression *& else_cond, Statement * settter, CompoundStmt * stmt );
127                Expression * call(size_t count, ObjectDecl * acceptables, Expression * timeout, CompoundStmt * stmt);
128                void         choose( WaitForStmt * waitfor, Expression  * result, CompoundStmt * stmt );
129
130                static void implement( std::list< Declaration * > & translationUnit ) {
131                        PassVisitor< GenerateWaitForPass > impl;
132                        mutateAll( translationUnit, impl );
133                }
134
135
136          private:
137                FunctionDecl        * decl_waitfor    = nullptr;
138                StructDecl          * decl_mask       = nullptr;
139                StructDecl          * decl_acceptable = nullptr;
140                StructDecl          * decl_monitor    = nullptr;
141
142                static std::unique_ptr< Type > generic_func;
143
144                UniqueName namer_acc = "__acceptables_"s;
145                UniqueName namer_idx = "__index_"s;
146                UniqueName namer_flg = "__do_run_"s;
147                UniqueName namer_msk = "__mask_"s;
148                UniqueName namer_mon = "__monitors_"s;
149                UniqueName namer_tim = "__timeout_"s;
150        };
151
152        //=============================================================================================
153        // General entry routine
154        //=============================================================================================
155        void generateWaitFor( std::list< Declaration * > & translationUnit ) {
156                GenerateWaitForPass     ::implement( translationUnit );
157        }
158
159        //=============================================================================================
160        // Generic helper routine
161        //=============================================================================================
162
163        namespace {
164                Expression * makeOpIndex( DeclarationWithType * array, unsigned long index ) {
165                        return new UntypedExpr(
166                                new NameExpr( "?[?]" ),
167                                {
168                                        new VariableExpr( array ),
169                                        new ConstantExpr( Constant::from_ulong( index ) )
170                                }
171                        );
172                }
173
174                Expression * makeOpAssign( Expression * lhs, Expression * rhs ) {
175                        return new UntypedExpr(
176                                        new NameExpr( "?=?" ),
177                                        { lhs, rhs }
178                        );
179                }
180
181                Expression * makeOpMember( Expression * sue, const std::string & mem ) {
182                        return new UntypedMemberExpr( new NameExpr( mem ), sue );
183                }
184
185                Statement * makeAccStatement( DeclarationWithType * object, unsigned long index, const std::string & member, Expression * value, const SymTab::Indexer & indexer ) {
186                        Expression * expr = makeOpAssign(
187                                makeOpMember(
188                                        makeOpIndex(
189                                                object,
190                                                index
191                                        ),
192                                        member
193                                ),
194                                value
195                        );
196
197                        ResolvExpr::findVoidExpression( expr, indexer );
198
199                        return new ExprStmt( expr );
200                }
201
202                Expression * safeCond( Expression * expr, bool ifnull = true ) {
203                        if( expr ) return expr;
204
205                        return new ConstantExpr( Constant::from_bool( ifnull ) );
206                }
207
208                VariableExpr * extractVariable( Expression * func ) {
209                        if( VariableExpr * var = dynamic_cast< VariableExpr * >( func ) ) {
210                                return var;
211                        }
212
213                        CastExpr * cast = strict_dynamic_cast< CastExpr * >( func );
214                        return strict_dynamic_cast< VariableExpr * >( cast->arg );
215                }
216
217                Expression * detectIsDtor( Expression * func ) {
218                        VariableExpr * typed_func = extractVariable( func );
219                        bool is_dtor = InitTweak::isDestructor( typed_func->var );
220                        return new ConstantExpr( Constant::from_bool( is_dtor ) );
221                }
222        };
223
224
225        //=============================================================================================
226        // Generate waitfor implementation
227        //=============================================================================================
228
229        void GenerateWaitForPass::premutate( FunctionDecl * decl) {
230                if( decl->name != "__waitfor_internal" ) return;
231
232                decl_waitfor = decl;
233        }
234
235        void GenerateWaitForPass::premutate( StructDecl   * decl ) {
236                if( ! decl->body ) return;
237
238                if( decl->name == "__acceptable_t" ) {
239                        assert( !decl_acceptable );
240                        decl_acceptable = decl;
241                }
242                else if( decl->name == "__waitfor_mask_t" ) {
243                        assert( !decl_mask );
244                        decl_mask = decl;
245                }
246                else if( decl->name == "$monitor" ) {
247                        assert( !decl_monitor );
248                        decl_monitor = decl;
249                }
250        }
251
252        Statement * GenerateWaitForPass::postmutate( WaitForStmt * waitfor ) {
253                if( !decl_monitor || !decl_acceptable || !decl_mask )
254                        SemanticError( waitfor, "waitfor keyword requires monitors to be in scope, add #include <monitor.hfa>" );
255
256                CompoundStmt * stmt = new CompoundStmt();
257
258                ObjectDecl * acceptables = declare( waitfor->clauses.size(), stmt );
259                ObjectDecl * flag        = declareFlag( stmt );
260                Statement  * setter      = makeSetter( flag );
261
262                int index = 0;
263                for( auto & clause : waitfor->clauses ) {
264                        init( acceptables, index, clause, setter, stmt );
265
266                        index++;
267                }
268
269                Expression * timeout = init_timeout(
270                        waitfor->timeout.time,
271                        waitfor->timeout.condition,
272                        waitfor->orelse .statement,
273                        waitfor->orelse .condition,
274                        setter,
275                        stmt
276                );
277
278                CompoundStmt * compound = new CompoundStmt();
279                stmt->push_back( new IfStmt(
280                        safeCond( new VariableExpr( flag ) ),
281                        compound,
282                        nullptr
283                ));
284
285                Expression * result = call( waitfor->clauses.size(), acceptables, timeout, compound );
286
287                choose( waitfor, result, compound );
288
289                return stmt;
290        }
291
292        ObjectDecl * GenerateWaitForPass::declare( unsigned long count, CompoundStmt * stmt )
293        {
294                ObjectDecl * acceptables = ObjectDecl::newObject(
295                        namer_acc.newName(),
296                        new ArrayType(
297                                noQualifiers,
298                                new StructInstType(
299                                        noQualifiers,
300                                        decl_acceptable
301                                ),
302                                new ConstantExpr( Constant::from_ulong( count ) ),
303                                false,
304                                false
305                        ),
306                        nullptr
307                );
308
309                stmt->push_back( new DeclStmt( acceptables) );
310
311                Expression * set = new UntypedExpr(
312                        new NameExpr( "__builtin_memset" ),
313                        {
314                                new VariableExpr( acceptables ),
315                                new ConstantExpr( Constant::from_int( 0 ) ),
316                                new SizeofExpr( new VariableExpr( acceptables ) )
317                        }
318                );
319
320                ResolvExpr::findVoidExpression( set, indexer );
321
322                stmt->push_back( new ExprStmt( set ) );
323
324                return acceptables;
325        }
326
327        ObjectDecl * GenerateWaitForPass::declareFlag( CompoundStmt * stmt ) {
328                ObjectDecl * flag = ObjectDecl::newObject(
329                        namer_flg.newName(),
330                        new BasicType(
331                                noQualifiers,
332                                BasicType::Bool
333                        ),
334                        new SingleInit( new ConstantExpr( Constant::from_ulong( 0 ) ) )
335                );
336
337                stmt->push_back( new DeclStmt( flag) );
338
339                return flag;
340        }
341
342        Statement * GenerateWaitForPass::makeSetter( ObjectDecl * flag ) {
343                Expression * expr = new UntypedExpr(
344                        new NameExpr( "?=?" ),
345                        {
346                                new VariableExpr( flag ),
347                                new ConstantExpr( Constant::from_ulong( 1 ) )
348                        }
349                );
350
351                ResolvExpr::findVoidExpression( expr, indexer );
352
353                return new ExprStmt( expr );
354        }
355
356        ObjectDecl * GenerateWaitForPass::declMon( WaitForStmt::Clause & clause, CompoundStmt * stmt ) {
357
358                ObjectDecl * mon = ObjectDecl::newObject(
359                        namer_mon.newName(),
360                        new ArrayType(
361                                noQualifiers,
362                                new PointerType(
363                                        noQualifiers,
364                                        new StructInstType(
365                                                noQualifiers,
366                                                decl_monitor
367                                        )
368                                ),
369                                new ConstantExpr( Constant::from_ulong( clause.target.arguments.size() ) ),
370                                false,
371                                false
372                        ),
373                        new ListInit(
374                                map_range < std::list<Initializer*> > ( clause.target.arguments, [this](Expression * expr ){
375                                        Expression * init = new CastExpr(
376                                                new UntypedExpr(
377                                                        new NameExpr( "get_monitor" ),
378                                                        { expr }
379                                                ),
380                                                new PointerType(
381                                                        noQualifiers,
382                                                        new StructInstType(
383                                                                noQualifiers,
384                                                                decl_monitor
385                                                        )
386                                                ),
387                                                false
388                                        );
389
390                                        ResolvExpr::findSingleExpression( init, indexer );
391                                        return new SingleInit( init );
392                                })
393                        )
394                );
395
396                stmt->push_back( new DeclStmt( mon) );
397
398                return mon;
399        }
400
401        void GenerateWaitForPass::init( ObjectDecl * acceptables, int index, WaitForStmt::Clause & clause, Statement * setter, CompoundStmt * stmt ) {
402
403                ObjectDecl * monitors = declMon( clause, stmt );
404
405                Type * fptr_t = new PointerType( noQualifiers, new FunctionType( noQualifiers, true ) );
406
407                stmt->push_back( new IfStmt(
408                        safeCond( clause.condition ),
409                        new CompoundStmt({
410                                makeAccStatement( acceptables, index, "is_dtor", detectIsDtor( clause.target.function )                                    , indexer ),
411                                makeAccStatement( acceptables, index, "func"   , new CastExpr( clause.target.function, fptr_t, false )                     , indexer ),
412                                makeAccStatement( acceptables, index, "data"   , new VariableExpr( monitors )                                              , indexer ),
413                                makeAccStatement( acceptables, index, "size"   , new ConstantExpr( Constant::from_ulong( clause.target.arguments.size() ) ), indexer ),
414                                setter->clone()
415                        }),
416                        nullptr
417                ));
418
419                clause.target.function = nullptr;
420                clause.target.arguments.empty();
421                clause.condition = nullptr;
422        }
423
424        Expression * GenerateWaitForPass::init_timeout(
425                Expression *& time,
426                Expression *& time_cond,
427                bool has_else,
428                Expression *& else_cond,
429                Statement * setter,
430                CompoundStmt * stmt
431        ) {
432                ObjectDecl * timeout = ObjectDecl::newObject(
433                        namer_tim.newName(),
434                        new BasicType(
435                                noQualifiers,
436                                BasicType::LongLongUnsignedInt
437                        ),
438                        new SingleInit(
439                                new ConstantExpr( Constant::from_int( -1 ) )
440                        )
441                );
442
443                stmt->push_back( new DeclStmt( timeout ) );
444
445                if( time ) {
446                        stmt->push_back( new IfStmt(
447                                safeCond( time_cond ),
448                                new CompoundStmt({
449                                        new ExprStmt(
450                                                makeOpAssign(
451                                                        new VariableExpr( timeout ),
452                                                        time
453                                                )
454                                        ),
455                                        setter->clone()
456                                }),
457                                nullptr
458                        ));
459
460                        time = time_cond = nullptr;
461                }
462
463                if( has_else ) {
464                        stmt->push_back( new IfStmt(
465                                safeCond( else_cond ),
466                                new CompoundStmt({
467                                        new ExprStmt(
468                                                makeOpAssign(
469                                                        new VariableExpr( timeout ),
470                                                        new ConstantExpr( Constant::from_ulong( 0 ) )
471                                                )
472                                        ),
473                                        setter->clone()
474                                }),
475                                nullptr
476                        ));
477
478                        else_cond = nullptr;
479                }
480
481                delete setter;
482
483                return new VariableExpr( timeout );
484        }
485
486        Expression * GenerateWaitForPass::call(
487                size_t count,
488                ObjectDecl * acceptables,
489                Expression * timeout,
490                CompoundStmt * stmt
491        ) {
492                ObjectDecl * index = ObjectDecl::newObject(
493                        namer_idx.newName(),
494                        new BasicType(
495                                noQualifiers,
496                                BasicType::ShortSignedInt
497                        ),
498                        new SingleInit(
499                                new ConstantExpr( Constant::from_int( -1 ) )
500                        )
501                );
502
503                stmt->push_back( new DeclStmt( index ) );
504
505                ObjectDecl * mask = ObjectDecl::newObject(
506                        namer_msk.newName(),
507                        new StructInstType(
508                                noQualifiers,
509                                decl_mask
510                        ),
511                        new ListInit({
512                                new SingleInit( new AddressExpr( new VariableExpr( index ) ) ),
513                                new ListInit({
514                                        new SingleInit( new VariableExpr( acceptables ) ),
515                                        new SingleInit( new ConstantExpr( Constant::from_ulong( count ) ) )
516                                })
517                        })
518                );
519
520                stmt->push_back( new DeclStmt( mask ) );
521
522                stmt->push_back( new ExprStmt(
523                        new ApplicationExpr(
524                                VariableExpr::functionPointer( decl_waitfor ),
525                                {
526                                        new CastExpr(
527                                                new VariableExpr( mask ),
528                                                new ReferenceType(
529                                                        noQualifiers,
530                                                        new StructInstType(
531                                                                noQualifiers,
532                                                                decl_mask
533                                                        )
534                                                ),
535                                                false
536                                        ),
537                                        timeout
538                                }
539                        )
540                ));
541
542                return new VariableExpr( index );
543        }
544
545        void GenerateWaitForPass::choose(
546                WaitForStmt * waitfor,
547                Expression  * result,
548                CompoundStmt * stmt
549        ) {
550                SwitchStmt * swtch = new SwitchStmt(
551                        result,
552                        std::list<Statement *>()
553                );
554
555                unsigned long i = 0;
556                for( auto & clause : waitfor->clauses ) {
557                        swtch->statements.push_back(
558                                new CaseStmt(
559                                        new ConstantExpr( Constant::from_ulong( i++ ) ),
560                                        {
561                                                new CompoundStmt({
562                                                        clause.statement,
563                                                        new BranchStmt(
564                                                                "",
565                                                                BranchStmt::Break
566                                                        )
567                                                })
568                                        }
569                                )
570                        );
571                }
572
573                if(waitfor->timeout.statement) {
574                        swtch->statements.push_back(
575                                new CaseStmt(
576                                        new ConstantExpr( Constant::from_int( -2 ) ),
577                                        {
578                                                new CompoundStmt({
579                                                        waitfor->timeout.statement,
580                                                        new BranchStmt(
581                                                                "",
582                                                                BranchStmt::Break
583                                                        )
584                                                })
585                                        }
586                                )
587                        );
588                }
589
590                if(waitfor->orelse.statement) {
591                        swtch->statements.push_back(
592                                new CaseStmt(
593                                        new ConstantExpr( Constant::from_int( -1 ) ),
594                                        {
595                                                new CompoundStmt({
596                                                        waitfor->orelse.statement,
597                                                        new BranchStmt(
598                                                                "",
599                                                                BranchStmt::Break
600                                                        )
601                                                })
602                                        }
603                                )
604                        );
605                }
606
607                stmt->push_back( swtch );
608        }
609};
610
611// Local Variables: //
612// mode: c //
613// tab-width: 4 //
614// End: //
Note: See TracBrowser for help on using the repository browser.